LeetCode:单词接龙算法实现与优化

题目

127. 单词接龙

给定两个单词(beginWord 和 endWord)和一个字典,找到从 beginWord 到 endWord 的最短转换序列的长度。转换需遵循如下规则:

每次转换只能改变一个字母。
转换过程中的中间单词必须是字典中的单词。

说明:

  • 如果不存在这样的转换序列,返回 0。
  • 所有单词具有相同的长度。
  • 所有单词只由小写字母组成。
  • 字典中不存在重复的单词。
  • 你可以假设 beginWord 和 endWord 是非空的,且二者不相同。

示例 1:

1
2
3
4
5
6
7
8
9
输入:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]

输出: 5

解释: 一个最短转换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog",
返回它的长度 5。

示例 2:

1
2
3
4
5
6
7
8
输入:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]

输出: 0

解释: endWord "cog" 不在字典中,所以无法进行转换。

BFS广度优先搜索 (1075ms)

这道题最容易想到的就是BFS广度优先搜索。

第一版代码如下,耗时1075 ms。

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
class Solution {
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
if (!wordList.contains(endWord)) {
return 0;
}
Set<String> visited = new HashSet<>();
Queue<String> queue = new LinkedList<>();
queue.offer(beginWord);
visited.add(beginWord);
int count = 0;
while (queue.size() > 0) {
int size = queue.size();
++count;
for (int i = 0; i < size; ++i) {
String start = queue.poll();
for (String s : wordList) {
// 已经遍历的不再重复遍历
if (visited.contains(s)) {
continue;
}
// 不能转换的直接跳过
if (!canConvert(start, s)) {
continue;
}
// 用于调试
// System.out.println(count + ": " + start + "->" + s);
// 可以转换,并且能转换成endWord,则返回count
if (s.equals(endWord)) {
return count + 1;
}
// 保存访问过的单词,同时把单词放进队列,用于下一层的访问
visited.add(s);
queue.offer(s);
}
}
}
return 0;
}

public boolean canConvert(String s1, String s2) {
if (s1.length() != s2.length()) return false;
int count = 0;
for (int i = 0; i < s1.length(); ++i) {
if (s1.charAt(i) != s2.charAt(i)) {
++count;
if (count > 1) {
return false;
}
}
}
return count == 1;
}
}

优化visited标记 (291ms)

第一版耗时太长,做了一点优化,把visited从HashSet改成boolean数组,通过index判断是否已访问。这样判断visited只需要boolean数组判断,节省了大量HashSet操作。耗时下降为291 ms。

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
class Solution {
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
if (!wordList.contains(endWord)) {
return 0;
}
// visited修改为boolean数组
boolean[] visited = new boolean[wordList.size()];
int idx = wordList.indexOf(beginWord);
if (idx != -1) {
visited[idx] = true;
}
Queue<String> queue = new LinkedList<>();
queue.offer(beginWord);
int count = 0;
while (queue.size() > 0) {
int size = queue.size();
++count;
while (size-- > 0) {
String start = queue.poll();
for (int i = 0; i < wordList.size(); ++i) {
// 通过index判断是否已经访问
if (visited[i]) {
continue;
}
String s = wordList.get(i);
if (!canConvert(start, s)) {
continue;
}
if (s.equals(endWord)) {
return count + 1;
}
visited[i] = true;
queue.offer(s);
}
}
}
return 0;
}

public boolean canConvert(String s1, String s2) {
// 因为题目说了单词长度相同,可以不考虑长度问题
// if (s1.length() != s2.length()) return false;
int count = 0;
for (int i = 0; i < s1.length(); ++i) {
if (s1.charAt(i) != s2.charAt(i)) {
++count;
if (count > 1) {
return false;
}
}
}
return count == 1;
}
}

双向BFS (840 ms)

简单浏览了一些题解,提到了使用双向BFS来实现,比BFS效率更高,因此实现了基本的双向BFS。结果很意外,耗时比直接用BFS反而更多了,变成了840ms。

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
class Solution {
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
int end = wordList.indexOf(endWord);
if (end == -1) {
return 0;
}
wordList.add(beginWord);
int start = wordList.size() - 1;
// 用于BFS遍历的队列
Queue<Integer> queue1 = new LinkedList<>();
Queue<Integer> queue2 = new LinkedList<>();
// 用于保存已访问的单词
Set<Integer> visited1 = new HashSet<>();
Set<Integer> visited2 = new HashSet<>();
queue1.offer(start);
queue2.offer(end);
visited1.add(start);
visited2.add(end);
int count1 = 0;
int count2 = 0;
while (!queue1.isEmpty() && !queue2.isEmpty()) {
count1++;
int size1 = queue1.size();
while (size1-- > 0) {
String s = wordList.get(queue1.poll());
for (int i = 0; i < wordList.size(); ++i) {
if (visited1.contains(i)) {
continue;
}
if (!canConvert(s, wordList.get(i))) {
continue;
}
if (visited2.contains(i)) {
return count1 + count2 + 1;
}
visited1.add(i);
queue1.offer(i);
}
}
count2++;
int size2 = queue2.size();
while (size2-- > 0) {
String s = wordList.get(queue2.poll());
for (int i = 0; i < wordList.size(); ++i) {
if (visited2.contains(i)) {
continue;
}
if (!canConvert(s, wordList.get(i))) {
continue;
}
if (visited1.contains(i)) {
return count1 + count2 + 1;
}
visited2.add(i);
queue2.offer(i);
}
}
}
return 0;
}

public boolean canConvert(String a, String b) {
int count = 0;
for (int i = 0; i < a.length(); ++i) {
if (a.charAt(i) != b.charAt(i)) {
if (++count > 1) return false;
}
}
return count == 1;
}
}

双向BFS优化 (133ms)

对双向BFS进行优化,主要的优化点就是每次遍历一层时,从节点更少的一端遍历。果然优化后耗时大大下降,变成了133ms。

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
class Solution {
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
int end = wordList.indexOf(endWord);
if (end == -1) {
return 0;
}
wordList.add(beginWord);
int start = wordList.size() - 1;
Queue<Integer> queue1 = new LinkedList<>();
Queue<Integer> queue2 = new LinkedList<>();
Set<Integer> visited1 = new HashSet<>();
Set<Integer> visited2 = new HashSet<>();
queue1.offer(start);
queue2.offer(end);
visited1.add(start);
visited2.add(end);
int count = 0;
while (!queue1.isEmpty() && !queue2.isEmpty()) {
count++;
if (queue1.size() > queue2.size()) {
Queue<Integer> tmp = queue1;
queue1 = queue2;
queue2 = tmp;
Set<Integer> t = visited1;
visited1 = visited2;
visited2 = t;
}
int size1 = queue1.size();
while (size1-- > 0) {
String s = wordList.get(queue1.poll());
for (int i = 0; i < wordList.size(); ++i) {
if (visited1.contains(i)) {
continue;
}
if (!canConvert(s, wordList.get(i))) {
continue;
}
if (visited2.contains(i)) {
return count + 1;
}
visited1.add(i);
queue1.offer(i);
}
}
}
return 0;
}

public boolean canConvert(String a, String b) {
int count = 0;
for (int i = 0; i < a.length(); ++i) {
if (a.charAt(i) != b.charAt(i)) {
if (++count > 1) return false;
}
}
return count == 1;
}
}

单词转换判断的优化 (23ms)

判断当前单词可以转换成哪些候选单词(未访问的单词),有两种思路:

  • **思路1:**遍历所有候选单词,判断当前单词是否可以转换成这个候选单词。判断的过程也就是前面的canConvert方法,逐个对比单词的字符。

  • **思路2:**因为单词是由a~z这有限数量的字符组成的,可以遍历当前单词能转换成的所有单词,判断其是否包含在候选单词中。候选单词用HashSet保存,可以大大提高判断包含关系的性能。

当单词总数量庞大的时候,之前代码用到的思路1耗时就会很长。而当单词的字符串数量、单词长度很大时,思路2耗时就会更长。实际情况下,一般单词不会很长,字符也是固定的26个小写字母,因此思路2的性能会好很多。

于是进一步优化代码,思路1改为思路2,性能提升很明显,耗时减少到了23ms。

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
class Solution {
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
int end = wordList.indexOf(endWord);
if (end == -1) {
return 0;
}
wordList.add(beginWord);

// 从两端BFS遍历要用的队列
Queue<String> queue1 = new LinkedList<>();
Queue<String> queue2 = new LinkedList<>();
// 两端已经遍历过的节点
Set<String> visited1 = new HashSet<>();
Set<String> visited2 = new HashSet<>();
queue1.offer(beginWord);
queue2.offer(endWord);
visited1.add(beginWord);
visited2.add(endWord);

int count = 0;
Set<String> allWordSet = new HashSet<>(wordList);

while (!queue1.isEmpty() && !queue2.isEmpty()) {
count++;
if (queue1.size() > queue2.size()) {
Queue<String> tmp = queue1;
queue1 = queue2;
queue2 = tmp;
Set<String> t = visited1;
visited1 = visited2;
visited2 = t;
}
int size1 = queue1.size();
while (size1-- > 0) {
String s = queue1.poll();
char[] chars = s.toCharArray();
for (int j = 0; j < s.length(); ++j) {
// 保存第j位的原始字符
char c0 = chars[j];
for (char c = 'a'; c <= 'z'; ++c) {
chars[j] = c;
String newString = new String(chars);
// 已经访问过了,跳过
if (visited1.contains(newString)) {
continue;
}
// 两端遍历相遇,结束遍历,返回count
if (visited2.contains(newString)) {
return count + 1;
}
// 如果单词在列表中存在,将其添加到队列,并标记为已访问
if (allWordSet.contains(newString)) {
queue1.offer(newString);
visited1.add(newString);
}
}
// 恢复第j位的原始字符
chars[j] = c0;
}
}
}
return 0;
}
}