Problem description:

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.

Solution:

The key idea is to substitute every single character in the beginWord and check whether if there’s any match in the wordList. One thing you need to notice is that you can not use a word twice; therefore, once a word in wordList is used(used means we can find a match after replacing the character), you need to remove it from the list.

Put wordList in set(), remove word if it’s used.
BFS to find if a word exist, newWord is newWord = word[:i] + c + word[i+1:]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        # put wordList into set
        # BFS to find if word exist
        wordSet = set(wordList)
        queue = deque()
        queue.append([beginWord, 1])
        
        while queue:
            word, length = queue.popleft()
            if word == endWord:
                return length
            for i in range(len(word)):
                for c in "abcdefghijklmnopqrstuvwxyz":
                    newWord = word[:i] + c + word[i+1:]
                    if newWord in wordSet:
                        wordSet.remove(newWord)
                        queue.append([newWord, length+1])
        return 0
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
class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> dict(wordList.begin(), wordList.end()); //put into unordered_set for efficient search
        if (!dict.count(endWord)) return 0;
        
        queue<string> q;
        q.push(beginWord);
        
        int l = beginWord.length();
        int step = 0;
        
        while (!q.empty()) {
            ++step;
            for (int size = q.size(); size > 0; size--) { 
                string w = q.front(); //pick a word in queue to do the search
                q.pop();
                for (int i = 0; i < l; i++) { //the description stated that the length of each word would be the same
                    char ch = w[i]; //change each character to find if there's a match
                    for (int j = 'a'; j <= 'z'; j++) {
                        w[i] = j;
                        // Found the solution
                        if (w == endWord) return step + 1;
                        
                        // Not in dict, skip it
                        if (!dict.count(w)) continue;
                        
                        // Remove new word from dict, because we can only use each word in dictionary once
                        dict.erase(w);
                        
                        // Add new word into queue
                        q.push(w);                    
                    }
                    w[i] = ch;
                }
            }
        }
        return 0;
    }
};

reference:
https://goo.gl/yJo3ou
https://goo.gl/JNAsQE