Word Ladder Problem


Description

LeetCode Problem 127.

A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence of words beginWord -> s_1 -> s_2 -> … -> s_k such that:

  • Every adjacent pair of words differs by a single letter.
  • Every s_i for 1 <= i <= k is in wordList. Note that beginWord does not need to be in wordList.
  • s_k == 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:

1
2
3
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:

1
2
3
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.


Sample C++ Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        int steps = 0;
        unordered_map<string, int> visited;
        
        for (int i = 0; i < wordList.size(); i ++) {
            visited[wordList[i]] = 0;
        }
        if (visited.find(endWord) == visited.end())
            return steps;
        
        queue<string> bfsQ;
        bfsQ.push(beginWord);
        int l;
        string curr, temp;
        bool found = false;
        while (!bfsQ.empty()) {
            l = bfsQ.size();
            for (int i = 0; i < l; i ++) {
                curr = bfsQ.front();
                bfsQ.pop();
                if (curr == endWord) {
                    found = true;
                    break;
                }
                for (int j = 0; j < curr.size(); j ++) {
                    temp = curr;
                    for (char c = 'a'; c <= 'z'; c ++) {
                        temp[j] = c;
                        if (visited.find(temp) != visited.end()) {
                            if (visited[temp] == 0) {
                                bfsQ.push(temp);
                                visited[temp] = 1;
                            }
                        }
                    }
                }
            }
            steps ++;
            if (found)
                break;
        }
        if (found)
            return steps;
        else
            return 0;
    }
};




Related Posts

Binary Tree Right Side View Problem

LeetCode 199. Given the root of a binary tree, imagine...

Word Ladder Problem

LeetCode 127. Given two words, beginWord and endWord, and a...

Word Ladder II Problem

LeetCode 126. Given two words, beginWord and endWord, and a...

Surrounded Regions Problem

LeetCode 130. Given an m x n matrix board containing...

Binary Tree Zigzag Level Order Traversal Problem

LeetCode 103. Given the root of a binary tree, return...

Binary Tree Level Order Traversal Problem

LeetCode 102. Given the root of a binary tree, return...