题目链接：Word Ladder
Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that:
- Only one letter can be changed at a time
- Each intermediate word must exist in the dictionary
For example,
Given:
start = “hit”
end = “cog”
dict = [“hot”,”dot”,”dog”,”lot”,”log”]
As one shortest transformation is “hit” -> “hot” -> “dot” -> “dog” -> “cog”,
return its length 5.
Note:
- Return 0 if there is no such transformation sequence.
- All words have the same length.
- All words contain only lowercase alphabetic characters.
这道题的要求是在两个单词间找到最短路径，其中路径是指由可以经过且只经过1个字符的改变并且在字典中的单词构成的。
-
广度优先搜索
可以注意到，字典中的不同单词，通过只有1个字符不同这条规则可以连接起来，进而构成“图”。而要求求最短路径，因此采用广度优先搜索：从start开始，查看字典中没有访问过的单词，找出是经过1个字符变换形成的，放入队列，就这样，逐层找下去，直到某一单词等于end时终止，此时层高就是最短路径。可惜，时间复杂度为O(nm)（n为访问单词数量，m为字典中单词总数），当字典里单词数量增加时，时间复杂度非常高，因此超时。
换一种思路，可以对每个路径上的单词中的每个字符进行替换处理，然后查找是否没访问过而且在字典中，如果是，这放入队列。这样直到某一单词等于end时终止，此时层高就是最短路径。时间复杂度为O(nlk)（n为访问单词数量，l为单词长度，k为字符数量26，l*k小于m），有所降低。
时间复杂度：O(nlk)（n为访问单词数量，l为单词长度，k为字符数量26）
空间复杂度：O(nl)（n为访问单词数量，l为单词长度）
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
class Solution
{
public:
int ladderLength(string start, string end, unordered_set<string> &dict)
{
// 标记字典中的单词是否被访问过
unordered_set<string> visited;
queue<string> q;
q.push(start);
visited.insert(start);
int height = 1;
while(!q.empty())
{
// 接下来处理下一层
++ height;
for(int i = 0, n = q.size(); i < n; ++ i)
{
string s = q.front();
q.pop();
// 对单词中的每个字符都进行替换处理
for(int j = 0; j < s.size(); ++ j)
{
string temp = s;
// 依次用26个字母进行替换
for(char c = 'a'; c <= 'z'; ++ c)
{
temp[j] = c;
// 如果替换后等于end，直接返回遍历的层高height即可
if(temp == end)
return height;
// 如果在字典中且没被访问过，入队列并标记为已访问
if(dict.find(temp) != dict.end() && visited.find(temp) == visited.end())
{
q.push(temp);
visited.insert(temp);
}
}
}
}
}
return 0;
}
};
-
双端查找
采用2个集合set1和set2表示从前往后遍历时每层的单词以及从后往前遍历时每层的单词，并且令set1为数量小的集合，这样每次均从set1（即数量小的集合）进一步查找下一层，目的是为了减少时间复杂度。直到某一集合为空，说明没有路径；或者直到两个集合相遇，返回遍历的层高height。
至于时间复杂度，个人认为还是O(nlk)（n为访问单词数量，l为单词长度，k为字符数量26），只不过通过双端查找的方式，每次均找数量小的集合查找，有效降低了n的数量。。。
时间复杂度：O(nlk)（n为访问单词数量，l为单词长度，k为字符数量26）
空间复杂度：O(nl)（n为访问单词数量，l为单词长度）
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
class Solution
{
public:
int ladderLength(string start, string end, unordered_set<string> &dict)
{
unordered_set<string> set1, set2, visited;
set1.insert(start); // 初始set1存储起始单词
set2.insert(end); // 初始set2存储结束单词
visited.insert(start);
visited.insert(end);
int height = 1;
// 只要set1或set2中有一个为空就说明没有路径
while(!set1.empty() && !set2.empty())
{
++ height;
// 将set1置为数量小的集合，每次都从set1中遍历查找下一层
if(set2.size() < set1.size())
swap(set1, set2);
// temps为临时set，存储set1的下一层
unordered_set<string> temps;
for(auto it = set1.begin(); it != set1.end(); ++ it)
{
string s = *it;
// 对单词中的每个字符都进行替换处理
for(int i = 0; i < s.size(); ++ i)
{
string temp = s;
// 依次用26个字母进行替换
for(char c = 'a'; c <= 'z'; ++ c)
{
temp[i] = c;
// 如果替换后单词在set2中，直接返回遍历的层高height即可
if(set2.find(temp) != set2.end())
return height;
// 如果在字典中且没被访问过，加入临时集合temps中并标记为已访问
if(dict.find(temp) != dict.end() && visited.find(temp) == visited.end())
{
temps.insert(temp);
visited.insert(temp);
}
}
}
}
set1 = temps; // 更新set1为其下一层（temps存储set1的下一层）
}
return 0;
}
};