127. Word Ladder

• Difficulty: Medium

• Topics: Breadth-first Search

• Similar Questions:

  • Word Ladder II

  • Minimum Genetic Mutation

Problem:

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.

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.

Solutions:

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> wordSet(wordList.begin(), wordList.end());
        if (wordSet.count(endWord) == 0)    return 0;
        unordered_set<string> q1;
        unordered_set<string> q2;
        q1.insert(beginWord);
        q2.insert(endWord);
        int n = beginWord.length();

        int level = 0;

        while (!(q1.empty() || q2.empty())) {
            ++level;
            int size1 = q1.size();
            int size2 = q2.size();

            if (size1 > size2) {
                swap(q1, q2);
            }

            unordered_set<string> q;

            for (string word : q1) {
                if (q2.count(word) > 0)    return level;

                for (int pos = 0; pos < n; ++pos) {
                    char origin = word[pos];
                    for (char letter = 'a'; letter <= 'z'; ++letter) {
                        word[pos] = letter;
                        if  (q1.count(word) == 0 && wordSet.count(word) > 0) {
                            q.insert(word);
                        }
                    }
                    word[pos] = origin;
                }
            }
            swap(q1, q);
        }

        return 0;
    }
};