广度优先搜索：单词梯子
点击“小风算法”，选择“设为星标”
大家好，我是小风哥，这是LeetCode刷题系列第9篇。
今天的题目是“单词梯子”，Leetcode第127号题目，要求是这样的：给定两个单词beginWord、endWord以及一个单词数组wordList，问我们能不能在wordList中找到从beginWord到endWord的一系列转化，要求每一次转化能改动一个字符，且找出需要转换次数最少的方案，看个示例理解的更清楚些。
给定beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]，那么一种转化次数最少的方案是："hit" -> "hot" -> "dot" -> "dog" -> cog"，注意除去beginWord 和endWord 其它单词必须出现在wordlist中，且中间的每次转换只能改动一个字符。
想一想该怎样解决这个问题。
这个问题的解决方法其实很直接，这无非就是一个搜索问题。
假设beginWord就是状态A，从状态A开始我们可能产出状态B、C、D，然后开枝散叶出去，状态B、C、D又可能会有各自的状态，就像这样：
状态A能产生哪些后续状态取决于当前单词能不能在wordlist中找到转换后的单词，按照刚才给出的示例，beginWord 也就是hit能在wordList 中找到一次转换为["hot"]，这样从hit这个状态就能产生一次后续状态“hot"。
你会发现这其实就是一个多叉树，我们需要找到状态为endWord的节点，并且从根节点到该节点的路径最短。
有了这个发现就简单了，树这种结构的搜索方式无非就是两种：广度优先搜索与深度优先搜索。
这两种方式都能解决问题，但考虑到这里需要找到最短路径，那么广度优先搜索天然适合解决最短路径问题。
因为广度优先搜索其实是一种层序遍历，只要我们能在某一层中首次发现该节点对应的单词等于endWord那么这一定是最短路径。
从上图看，如果节点D是第一个等于endWord的节点，那么路径A->D就是我们要找的答案。
有了这些分析代码就简单了。
我们首先利用map<string, vector<string>> 找出每个单词对应的转换，这样方便我们找到每个单词的下一个转换：
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
map<string, vector<string>> dic;
wordList.push_back(beginWord);
int wordListLen = wordList.size();
for (int i = 0; i < wordListLen; i++) {
for (int j = 0; j < wordListLen; j++) {
if (is_one_diff(wordList[i], wordList[j])) {
dic[wordList[i]].push_back(wordList[j]);
}
}
}
...
}
其中is_one_diff非常简单，无非就是判断两个字符串是否只相差一个字符：
bool is_one_diff(string& a, string& b) {
int len = a.length();
int diff_num = 0;
for (int i = 0; i < len; i++) {
if (a[i] != b[i]) ++diff_num;
if (diff_num > 1) return false;
}
return diff_num == 1;
}
最后利用广度优先遍历找到最短的转换，完整代码为：
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
map<string, vector<string>> dic;
wordList.push_back(beginWord);
int wordListLen = wordList.size();
for (int i = 0; i < wordListLen; i++) {
for (int j = 0; j < wordListLen; j++) {
if (is_one_diff(wordList[i], wordList[j])) {
dic[wordList[i]].push_back(wordList[j]);
}
}
}
vector<string> q;
q.push_back(beginWord);
int level = 0;
map<string, bool> used;
used[beginWord] = true;
while(!q.empty()) {
++level;
vector<string> tmp_q;
for (auto& s: q) {
if (s == endWord) {
return level;
}
for (auto& next_level_s : dic[s]) {
if (!used[next_level_s]) {
tmp_q.push_back(next_level_s);
used[next_level_s] = true;
}
}
}
swap(q, tmp_q);
}
return 0;
}