127. Word Ladder

Description

A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence of words beginWord -> s1 -> s2 -> ... -> sk such that:

• Every adjacent pair of words differs by a single letter.
• Every si for 1 <= i <= k is in wordList. Note that beginWord does not need to be in wordList.
• sk == endWord

Given two words, beginWord and endWord, and a dictionary wordList, return the number of words in the shortest transformation sequence from beginWord to endWord, or 0 if no such sequence exists.

Example 1:

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Output: 5
Explanation: One shortest transformation sequence is "hit" -> "hot" -> "dot" -> "dog" -> cog", which is 5 words long.

Example 2:

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
Output: 0
Explanation: The endWord "cog" is not in wordList, therefore there is no valid transformation sequence.

Constraints:

• 1 <= beginWord.length <= 10
• endWord.length == beginWord.length
• 1 <= wordList.length <= 5000
• wordList[i].length == beginWord.length
• beginWord, endWord, and wordList[i] consist of lowercase English letters.
• beginWord != endWord
• All the words in wordList are unique.

---

Solutions

Solution 1

Intuition

BFS

Code

class Solution
{
    public:
        int ladderLength(string beginWord, string endWord, vector<string> &wordList)
        {
            unordered_set<string> set;
            for (string &word: wordList) set.insert(word);
            unordered_map<string, int> dist;
            dist[beginWord] = 0;
            queue<string> q;
            q.push(beginWord);

            while (!q.empty())
            {
                string word = q.front(), next = word;
                q.pop();

                for (int i = 0; i < next.size(); i++)
                {
                    next = word;
                    for (char c = 'a'; c <= 'z'; c++)
                    {
                        // change one char in next from a to z
                        next[i] = c;
                        if (set.count(next) && !dist.count(next))
                        {
                            dist[next] = dist[word] + 1;
                            if (next == endWord)
                            {
                                return dist[next] + 1;
                            }
                            q.push(next);
                        }
                    }
                }
            }

            return 0;
        }
};

Complexity

• Time: BigO(M^2 * N), where M is size of dequeued word & N is size of our word list
• Space: BigO(M * N) where M is no. of character that we had in our string & N is the size of our wordList.

---