word-ladder.cpp

// Given two words (beginWord and endWord), and a dictionary's word list, find the length of shortest transformation sequence from beginWord to endWord, such that:
//
//
// 	Only one letter can be changed at a time.
// 	Each transformed word must exist in the word list. Note that beginWord is not a transformed word.
//
//
// Note:
//
//
// 	Return 0 if there is no such transformation sequence.
// 	All words have the same length.
// 	All words contain only lowercase alphabetic characters.
// 	You may assume no duplicates in the word list.
// 	You may assume beginWord and endWord are non-empty and are not the same.
//
//
// Example 1:
//
//
// Input:
// beginWord = "hit",
// endWord = "cog",
// wordList = ["hot","dot","dog","lot","log","cog"]
//
// Output: 5
//
// Explanation: As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
// return its length 5.
//
//
// Example 2:
//
//
// Input:
// beginWord = "hit"
// endWord = "cog"
// wordList = ["hot","dot","dog","lot","log"]
//
// Output: 0
//
// Explanation: The endWord "cog" is not in wordList, therefore no possible transformation.
//
//
//
//
//


class Solution {
public:
    int ladderLength(string beginWord, string endWord, unordered_set<string>& wordList) {
        if (beginWord == endWord) return 0;
        std::queue<string> q;
        std::unordered_map<string, int> level;
        q.push(beginWord);
        level[beginWord] = 1;
        while (!q.empty()) {
            string p = q.front();
            q.pop();
            for (int i = 0;i < p.size();++i) {
                string pp = p;
                for (char l = 'a'; l <= 'z'; ++l) {
                    if (p[i] == l) continue;
                    pp[i] = l;
                    if (pp == endWord) return level[p]+1;
                    if (wordList.find(pp) != wordList.end() && level[pp]==0) {
                        q.push(pp);
                        level[pp] = level[p]+1;
                    }
                }
            }
        }
        return 0;
    }
};