127. Word Ladder (Medium)

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:

1. Only one letter can be changed at a time.
2. Each transformed word must exist in the word list. Note that beginWord is not a transformed word. For example,

Given: beginWord = "hit" endWord = "cog" wordList = ["hot","dot","dog","lot","log","cog"] As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog", return its length 5.

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.

UPDATE (2017/1/20): The wordList parameter had been changed to a list of strings (instead of a set of strings). Please reload the code definition to get the latest changes.

Solution 1: BFS 129ms

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        unordered_map<string, int> m;
        for (string& w: wordList) m[w] = 0;

        queue<string> q; 
        q.push(beginWord);
        m[beginWord] = 1;
        while (!q.empty()) {
            string word = q.front(); q.pop();
            if (word == endWord) return m[word];
            for (int i = 0; i < word.size(); ++i) {
                string newWord = word;
                for (char c = 'a'; c <= 'z'; ++c) {
                    newWord[i] = c;
                    // new word exists and unvisited
                    if (m.count(newWord) && m[newWord] == 0) {
                        m[newWord] = m[word]+1;
                        q.push(newWord);
                    }
                }
            }

        }
        return 0;
    }
};

Solution 2: two-end BFS 32ms

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> dict, begSet, endSet, *set1, *set2;
        for (auto& w: wordList) dict.insert(w);
        begSet.insert(beginWord);
        endSet.insert(endWord);
        if (!dict.count(endWord)) return 0;
        int dist = 2;
        while (!begSet.empty() && !endSet.empty()) {
            if (begSet.size() <= endSet.size()) {
                set1 = &begSet, set2 = &endSet;
            } else {
                set2 = &begSet, set1 = &endSet;
            }
            unordered_set<string> tmp;
            for (auto it = set1->begin(); it != set1->end();it++) {
                string w = *it;
                for (int i = 0; i < w.size(); ++i) {
                    char letter = w[i];
                    for (char c = 'a'; c <= 'z'; ++c) {
                        w[i] = c;
                        if (set2->count(w)) return dist;
                        if (dict.count(w)) {
                            tmp.insert(w); dict.erase(w);
                        }
                    }
                    w[i] = letter;
                }

            }
            ++dist;
            swap(*set1, tmp);
        }
        return 0;
    }
};

class Solution {
public:
    int ladderLength(std::string beginWord, std::string endWord, std::unordered_set<std::string> &dict) {
        if (beginWord == endWord)
            return 1;
        std::unordered_set<std::string> words1, words2;
        words1.insert(beginWord);
        words2.insert(endWord);
        dict.erase(beginWord);
        dict.erase(endWord);
        return ladderLengthHelper(words1, words2, dict, 1);
    }

private:
    int ladderLengthHelper(std::unordered_set<std::string> &words1, std::unordered_set<std::string> &words2, std::unordered_set<std::string> &dict, int level) {
        if (words1.empty())
            return 0;
        if (words1.size() > words2.size())
            return ladderLengthHelper(words2, words1, dict, level);
        std::unordered_set<std::string> words3;
        for (auto it = words1.begin(); it != words1.end(); ++it) {
            std::string word = *it;
            for (auto ch = word.begin(); ch != word.end(); ++ch) {
                char tmp = *ch;
                for (*ch = 'a'; *ch <= 'z'; ++(*ch))
                    if (*ch != tmp)
                        if (words2.find(word) != words2.end())
                            return level + 1;
                        else if (dict.find(word) != dict.end()) {
                            dict.erase(word);
                            words3.insert(word);
                        }
                *ch = tmp;
            }
        }
        return ladderLengthHelper(words2, words3, dict, level + 1);
    }
};