1 题目
题目：单词接龙（Word Ladder）
描述：给出两个单词（start和end）和一个字典，找出从start到end的最短转换序列，输出最短序列的长度。变换规则如下：每次只能改变一个字母。变换过程中的中间单词必须在字典中出现。(起始单词和结束单词不需要出现在字典中)
- 如果不存在这样的转换序列，返回 0。
- 所有单词具有相同的长度。
- 所有单词只由小写字母组成。
- 字典中不存在重复的单词。
- 你可以假设 beginWord 和 endWord 是非空的，且二者不相同。
lintcode题号——120，难度——hard
样例1：
输入：
start = "a"
end = "c"
dict =["a","b","c"]
输出：2
解释："a"->"c"
样例2：
输入：
start ="hit"
end = "cog"
dict =["hot","dot","dog","lot","log"]
输出：5
解释："hit"->"hot"->"dot"->"dog"->"cog"
2 解决方案
2.1 思路
??根据题意画出dict中单词的转换路径图，给定了起点和终点，则题目转换为要找图中的最短路径长度，使用宽度优先搜索，由于要计算步数的长度，宽搜过程需要按层搜索，直到找到终点。
2.2 图解
示例：
start =“hit”,end = “cog”,dict =[“hot”,“dot”,“dog”,“lot”,“log”]
建立的转换图如下：
按照从起点“hit”按照宽度优先搜索的方式进行层级遍历，第一层找到”hot“，第二层找到“dot”和“lot”，第三层找到“dog”和“log”，第四层找到了终点“cog”，经历了四步，长度为5。
如果直接在dict中进行查找，在dict中找到节点所有邻接节点需要遍历一次字典，耗时为O(n)，其中n为dict中单词的数量。
考虑使用替换单词中的字母的方式，长度为L的单词，每个字母能替换成另外25个不同的字母，产生的可转换单词数量为L*25，在哈希表dict中查找长度为L的单词是否存在的耗时为O(L)，所以能够在O(25*L*L)的时间内完成搜索。
在字典规模很大的时候O(25*L*L) < O(n)，使用替换字母的方式要更优。
2.2 时间复杂度
??宽度优先搜索遍历所有的n个节点，每个节点的处理时间为O(25*L*L)，算法的时间复杂度为O(n*L*L)，其中n为单词数，L为单词长度。
2.3 空间复杂度
??图上的宽度优先搜索，使用了queue队列数据结构保存节点，算法的空间复杂度为O(n)。
3 源码
细节：
- 使用宽度优先搜索。
- 使用逐个字母替换并在字典中查询的方式，它比直接在字典中寻找相邻节点的方式在字典规模大的时候更优。
- 使用哈希set来防止转换成已经处理过的单词。
C++版本：
/**
* @param start: a string
* @param end: a string
* @param dict: a set of string
* @return: An integer
*/
int ladderLength(string &start, string &end, unordered_set<string> &dict) {
// write your code here
if (start == end)
{
return 1;
}
queue<string> strQueue;
unordered_set<string> duplicateSet; // 用于记录已经走过的单词
strQueue.push(start);
duplicateSet.insert(start);
int length = 1;
while (!strQueue.empty())
{
int size = strQueue.size();
for (int i = 0; i < size; i++)
{
string originalStr = strQueue.front();
strQueue.pop();
for (int j = 0; j < originalStr.size(); j++)
{
string str = originalStr;
for (char c = 'a'; c < 'z'; c++) // dict很大的时候，使用逐个替换字母的方式，比构造临接表更优
{
if (str.at(j) == c) // 遇到原字母，跳过
{
continue;
}
str.at(j) = c; // 替换单词中的一个字母
if (str == end) // 找到目标
{
return length + 1; // 返回当前长度加1
}
if (duplicateSet.find(str) == duplicateSet.end()
&& dict.find(str) != dict.end()) // 不重复且在字典中
{
strQueue.push(str);
duplicateSet.insert(str);
}
}
}
}
length++;
}
return 0;
}
