深度解析一道单词变换算法题

本文将深度地解析一道单词变换的算法题，因为这道题组合了一些常用的编程方法，具有比较典型的特点。

题目如下：
给定2个英文单词： 一个 beginWord，一个 endWord，以及一个字典（即单词列表）；
要求： 给出从 beginWord 到 endWord 的所有最短变换序列。
说明：

1. 所有单词都只由小写字母构成
2. 所有单词的长度都相同
3. 一次单词变换只能改变一个字符，如 cat->cot
4. beginWord 可以不在字典中
5. endWord 必须在字典中，否则认为无法完成转换

举例：

beginWord: red
endWord: tax
Dict: {"ted","tex","red","tax","tad","den","rex","pee"}
所有最短变换序列：
  red -> ted -> tex -> tax
  red -> rex -> tex -> tax
  red -> ted -> tad -> tax
1
2
3
4
5
6
7

思考：
这里要求给出所有的最短变换序列。这个要求比较高，第一是要最短的变换序列，第二是要所有的。
那么，自然地延伸出2个思路：

1. 找出所有的变化路径，然后再找出这其中最短的；
2. 是否可能直接找出所有的最短变换路径呢？ 那怎么确定这条变换路径就是最短的呢？

可能很多人首先会自然地思考，怎么找到一条这样的变换路径；然后就会想到，一条变换路径中可能出现多次循环甚至无穷循环的情况，大约应该用一个 visited 数组来标记一个单词是否已经出现在变换路径中。
由以上这些，就会进一步想到 – 这好像可以通过回溯法来做啊！ 就像走迷宫那样： 对于一个单词，有几种变换的可能，依次去试，等试到死胡同的时候，就回退原处，接着试下一种。
这似乎是一条思路，但于这道题却并不合适：
第一，回溯法其实是一种DFS（深度优先搜索），而这里要求的是最短变换路径，DFS并不合适，因为如果不求出所有的解，DFS就无法证明哪些是最短的；
第二，这里会有回环的情况，一旦是一个大的回环，就会浪费很多的时间，而且程序的实现也会非常复杂。
由此可见，上面两条思路的第一条，并不适合这道题。

那么，能不能做到第二条思路，即直接找到最短的变换路径，并且能够找到所有的呢？
其实，这是可以的。DFS不合适的话，BFS（广度优先搜索）呢？
将单词的变化想象成一棵树，beginWord就是树根，即树的第一层； 它所有的一次变换能达到的单词，就是树的第二层；
第二层的每一个单词就是一个的节点，每个节点的下一层节点就是这个节点单词的一次变换所能达到的所有单词；
依次类推，看 endWord 最早出现在哪一层上，那这就是最短变换路径的长度了。
貌似BFS可以比较方便地找到最短路径有多短，那么如何找到具体的最短变换路径，以及如何找到所有的呢？
有以下大约6个具体问题须一一思考解答。

问题-1. 如何处理回环的情况?

要回答这个问题，首先要回答另一个问题，如何识别回环？
这个答案貌似简单： 曾经出现过的单词，就不应该再出现了。
可惜这个答案并不精确。精确的答案是： 已经在更高层出现过的单词，就不该在本层出现了。

那么，如果在树的某一层出现过的单词，是否还能再次出现在该层呢？
这个问题比较重要。从识别回环的角度，或许在同层出现重复的单词是可以的，不会造成回环；但是这会造成在下一层出现重复的2块节点。比如，第n层第i个节点是单词abc，第n层第j个节点也是单词abc，那么在第n+1层上，n.i 节点的会生成若干子节点， 它和 n.j 节点生成的若干子节点就完全一样， 进而到 n+2 层上就会出现更多的重复节点了。
这会带来两个问题：

1. 指数级增长的冗余计算
2. 最后统计所有最短变换路径时，可能会出现重复的情况（如果应用问题-5的答案的解法）

所以，答案是，一个节点在同层也只能出现一次；或者说，这棵树中所有的单词都只会出现一次。

此时，就会引出另一个疑问，在 n-1 层上，n.i 和 n.j 的父节点并不相同，那怎么保证将来在计算所有最短变换路径时不会遗漏掉这 n-1 层上的2个节点中的任何一个呢？
这个其实不难。我们在问题-5中会加以解决。

回过头来，深入思考，如何知道一个单词是否出现在高层中呢？ 以及如何知道一个单词是否出现在这棵树中呢？
从以上的分析，我们只要解决后一个问题就够了；但其实不然，我们还是需要区分这个单词是出现在高层，还是出现在本层。这是因为：如果是在高层出现过，我们就可以直接忽略这个单词了；但如果高层没有出现过而却在本层出现过，那么还需要记录下该单词在本层出现时所有的父节点。这是为了最后统计所有的最短路径。（见问题-5）
要知道一个单词是否在高层出现过，有一个编程技巧：设定一个Hash表visited，key是单词，value就是这个单词出现的层数。于是判断就很简单了，检查 visited.count(word) && visited[word] < currentLayerIndex, 如果该条件成立，则不将该单词入队，即不记录在本层。
而判断一个单词是否出现在树中，就更简单了，即 !visited.count(word) .

问题-2.如何搜索某一特定层的所有单词，看是否存在endWord

之所以提出这个问题，是因为我们不知道 endWord 第一次会出现在哪一层上，于是我们希望一层一层地找。
要回答这个问题，首先我们需要回忆一下普通的 BFS 是怎么做的。比如，如何做树的层次序打印？ 然后对其加以改进。
树的层次序打印一般这么做： 给定一个queue，入队根节点，然后在while循环中出队一个节点，并入队这个节点的所有子节点。
伪代码如下：

queue<string> q;
q.push(beginWord); 

while (!q.empty()) {
    string word = q.top();
    q.pop();
    for(string word : one_char_diff_vector) {
        q.push(word);
    }
}
1
2
3
4
5
6
7
8
9
10

由以上代码可以看出，此时并没有特定层所有节点的标识，但是特定层所有节点都是连续入队的，并且稍改一下程序，也会很容易知道当前出队的是哪一层。 那么，看起来要遍历特定层的所有节点，也就不难以实现了。伪代码如下：

int currLevel = 0;

queue<string> q;
q.push(beginWord); 

while (!q.empty()) {
    // 取得当前的 queue size 
    int queueSize = q.size(); 

    for(int cnt = 0; cnt < queueSize; cnt++) {
        string currWord = q.front();
        q.pop();
        
        // Do some check and push into the queue 
        ...
    }

    currLevel ++; 
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

以上程序应用了一个技巧，即，在 while 循环的一开始，就取得当前 queue 的 size，而这就是上一层的所有节点了；至于在这个size之后继续入队的，就不是上一层的了。
试想，如果只入队了 beginWord， 那么这里取出的就是第0层的所有节点，即一个节点。
然后，用一个 for 循环来遍历上一层的所有节点，将它们一一 pop 出队列，此时就能得到当前层的所有节点，接着就可以对当前层的所有节点一一做检查操作了。比如，如果即将入队的这个节点，它在 visited 哈希表中已经出现过，并且是在更高层出现的，那么就不能入队了。

问题-3. 何时入队呢？

这个问题需要非常小心，但其实结论在分析问题-1的后半部分时，已经初具雏形了。

当这个节点符合以下2个条件，就可以入队了：
1> 该单词是当前出队单词的一次变换单词；
2> 在更高层和本层中都没有出现过，即在整个假想树中没有出现过，即 visited.count(word) == 0

注意， 如果这个单词在本层中出现过，虽然我们不再将它入队，但必须记录下它在上层中的所有父节点，因为将来要找出所有最短路径。（关于找出所有最短变换路径，参见问题-5。）

总结以上的逻辑：
如果该单词是上一层某单词的一次变换，那么：

1. 如果该单词在比当前层更高的层中出现过，那么不入队，也无须记录父节点；
2. 如果该单词没有在更高层中出现过，但是在本层中出现过，需记录父节点；
3. 如果该单词从未出现过，也需记录父节点；
4. 如果该单词从未出现过，则将该单词入队，即相当于加入了假想树的当前层；

相关代码如下：

    if(visited.count(nextWord) && visited[nextWord] < currLevel) continue;  // 不入队，也无须记录父节点

    parents[nextWord].push_back(currWord);  // 从未出现过，或同层出现过，则须记录其父节点

    if(!visited.count(nextWord)) {  // 从未出现过，则入队，相当于加入在假想树的当前层
        q.push(nextWord);
        visited[nextWord] = currLevel;
    }
1
2
3
4
5
6
7
8

问题-4. 怎么知道一个单词的所有一次变换单词是哪些单词呢？

这个问题不难，有多种实现方法。
方法一，事先计算好每个单词在单词表中的一次变换单词列表，并将其保存下来。
方法二，临时列举出给定单词的所有一次变换单词，然后将那些没有出现在单词表中的一次变换单词给过滤掉。

这里本以为方法一会更快，因为它是一种查表法；但实际上测下来，方法二更快。这可能是由于方法一相当于为整个字典的所有单词都计算了“一次变换”单词列表，反而导致了大量不必要的计算。
另外，方法二的实现代码更简洁一些。
因此本文最后的代码就以方法二为准了。

问题-5. 在当前层发现 endWord 之后，怎么收集到它的整条变换路径，以及所有变换路径？

这也是一个需要小小技巧的问题。
试想，如果此时我们知道 endWord 在上一层中的所有父节点，而对于这上一层中的每一个父节点，又知道它们在更上一层的父节点，则可以顺藤摸瓜，一直回溯到 beginWord 了。
具体方法是：
设定一个哈希表parents，由它来存储每一个节点的父节点列表。哈希表的key就是一个word，value就是一个vector，存放了这个word的所有父节点。

有了这张哈希表 parents， 怎么找到 endWord 到 beginWord 的所有路径呢？
这本身就是一道编程题。这个时候，DFS要上场了。惊不惊喜，意不意外？一道题竟同时囊括了BFS和DFS. 其实这也是一个递归的方法。 代码如下：

unordered_map<string, vector<string>> parents;
vector<vector<string>> result;
vector<string> path;

void dfs(string& beginWord, string& currWord)
{
    path.push_back(currWord);
    
    if (currWord == beginWord) {
        result.push_back(path);
        path.pop_back();
        return;
    }
    
    for (string& word : parents[currWord]) {
        dfs(beginWord, word);
    }

    path.pop_back();
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

这里要注意的一个小细节是，path里的单词顺序是从 endWord 到 beginWord 的，怎么把它反转过来？
自己写一段代码当然很简单。不过还有更简单的方法。如下：

#include 

for (auto& path : result) reverse(path.begin(), path.end())；
1
2
3

问题-6. while循环什么时候停下来？

这个问题比较简单。设定一个flag，用来标识是否已经发现了 endWord . 如果已经发现了，则本层做完后就从 while 循环中退出。
另外，如果根本发现不了endWord，那么queue最终会为空，此时也要结束while循环。

bool bHit = false;

while(!q.empty() && !bHit) {
    ...
    if (nextWord == endWord) bHit = true;
    ...
}

1
2
3
4
5
6
7
8

至此，关键的几个问题基本都已经得到解答。将上面的代码拼接起来，就是最后的程序了。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

vector<vector<string>> res;
unordered_map<string, vector<string>> parents;
vector<string> path;

template <class T>
void printVector(vector<T>& vec)
{
    for (auto & v : vec) cout << v << " ";
    cout << endl;
}

template <class T>
void printVector2D(vector<vector<T>> & vec2d)
{
    for (auto & vec : vec2d) printVector(vec);
    cout << endl;
}

void dfs(string& beginWord, string& currWord) {
    path.push_back(currWord);

    if(currWord == beginWord) {
        res.push_back(path);
        path.pop_back();
        return;
    }

    for(auto& nextWord : parents[currWord]) 
        dfs(beginWord, nextWord);

    path.pop_back();
}

vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
    unordered_set<string> wordSet(wordList.begin(), wordList.end());
    unordered_map<string, int> visited;

    int currLevel = 0;
    bool bHit = false; 
    
    queue<string> q;
    q.push(beginWord);

    while(!q.empty() && !bHit) {
        int queueSize = q.size();
        
        // This for loop calculates all the words in current layer, as queueSize has been fixed 
        for(int cnt = 0; cnt < queueSize; cnt++) {
            string currWord = q.front();
            q.pop();

            for(int indexOfDiffrentCharacter = 0; indexOfDiffrentCharacter < currWord.size(); indexOfDiffrentCharacter++) {
                for(char diffCharacter = 'a'; diffCharacter <= 'z'; diffCharacter++) {
                    string nextWord = currWord;
                    nextWord[indexOfDiffrentCharacter] = diffCharacter;

                    // Invalid word, continue 
                    if(!wordSet.count(nextWord)) continue;

                    // The word has already existed on higher level of the word tree, 
                    // so no need to record it in current level, continue 
                    if(visited.count(nextWord) && visited[nextWord] < currLevel) continue;

                    // Need to record parents for "visited[nextWord] == currLevel" 
                    parents[nextWord].push_back(currWord);

                    // Push to the queue only when this word never appears, 
                    // also no appears in current layer 
                    if(!visited.count(nextWord)) {
                        q.push(nextWord);
                        visited[nextWord] = currLevel;
                    }
                    
                    if(nextWord == endWord) bHit = true;
                }
            }
        }

        currLevel++;
    }

    dfs(beginWord, endWord);
    
    for(auto& path : res) reverse(path.begin(), path.end());
    
    return res;
}

int main()
{
    string beginWord = "red";
    string endWord = "tax";
    vector<string> wordList = {"ted","tex","red","tax","tad","den","rex","pee"};
    vector<vector<string>> result = findLadders(beginWord, endWord, wordList);
    printVector2D(result);
    
    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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107

(完)