Problem description:

Given two words (beginWord and endWord), and a dictionary’s word list, find all shortest transformation sequence(s) 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 an empty list 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:
[
[“hit”,”hot”,”dot”,”dog”,”cog”],
[“hit”,”hot”,”lot”,”log”,”cog”]
]
Example 2:

Input:
beginWord = “hit”
endWord = “cog”
wordList = [“hot”,”dot”,”dog”,”lot”,”log”]

Output: []

Explanation: The endWord “cog” is not in wordList, therefore no possible transformation.

Solution:

  1. Do BFS layer by layer
  2. After a layer is done, remove the newLayer keys from wordSet. This is to prevent loop. Note that we don’t remove from set when adding newWord, this is because other traverse in the same layer might still use it
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) -> List[List[str]]:
        wordSet = set(wordList)
        paths = {}
        paths[beginWord] =[[beginWord]]
        
        while paths:
            nextLayer = defaultdict(list) # need to keep all possible for next path
            for key in paths: # every current layer words
                if key == endWord:
                    return paths[key]
                for i in range(len(key)):
                    for c in "abcdefghijklmnopqrstuvwxyz":
                        newWord = key[:i]+c+key[i+1:]
                        if newWord in wordSet:
                            # append the newWrod after existed path
                            nextLayer[newWord] += [j + [newWord] for j in paths[key]] 
            wordSet -= set(nextLayer.keys()) # remove existed keys for next round after traversed all paths
            paths = nextLayer
        return []

This is a follow up for 127. Word Ladder. If you have this question on interview, maybe go with a naive BFS solution, then improve it with bi-direction BFS.

The solution came with one direction BFS, the step is as follows.

  1. Use BFS to solve question, so we need a queue. queue<vector<string>> paths, to store the paths in current level.
  2. A dictionary that help to search if a mutate string is in wordlist. The mutate string is created by the same method in 127. Word Ladder. For each character in a word, try to change it to another character, and check whether if it’s in the dictionary.
  3. Once we know the words in previous level(can think of as the BFS level), we can not use those words again, so we need a set(unordered_set<string> words) to record the used string on this level.
  4. Maintain a minlevel to speed up the process. Because if we can find a path to find endWord in 5 hops, then we don’t need to find any path that is greater than 5.
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
50
51
class Solution {
public:
    vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
        vector<vector<string>> res; 
        unordered_set<string> dict(wordList.begin(), wordList.end()); //for lookup if the changed word in dictionary or not
        vector<string> p{beginWord}; 
        queue<vector<string>> paths;
        
        paths.push(p);
        int level = 1, minLevel = INT_MAX;
        unordered_set<string> words;
        
        while (!paths.empty()) {
            auto t = paths.front(); //start with beginWord
            paths.pop();
            
            if (t.size() > level) {
                for (string w : words) dict.erase(w); //to remove the word that already used on level 1
                words.clear();
                level = t.size();
                if (level > minLevel) break;
            }
            string last = t.back(); //last element of curent path, try to find next word to link
            for (int i = 0; i < last.size(); ++i) {
                string newLast = last;
                for (char ch = 'a'; ch <= 'z'; ++ch) {
                    newLast[i] = ch;
                    if (!dict.count(newLast)) continue; 
                    
                    //can find another word after changing one character in dictionary
                    words.insert(newLast); //put it into set, so we won't use it again
                    
                    /*
                    example: 
                    t: abc->abd->acd
                    newPath= abc->abd->acd + acc
                    */
                    vector<string> nextPath = t; 
                    nextPath.push_back(newLast);

                    if (newLast == endWord) {
                        res.push_back(nextPath);
                        minLevel = level;
                    } 
                    else paths.push(nextPath);
                }
            }
        }
        return res;
    }
};

reference:
https://www.youtube.com/watch?v=lmypbtgdpuQ
http://www.cnblogs.com/grandyang/p/4548184.html
https://goo.gl/4rcWS6
https://goo.gl/t1vxXg