127 Word Ladder

127. Word Ladder

1. Question

Given two words (beginWordandendWord), and a dictionary's word list, find all shortest transformation sequence(s) frombeginWordtoendWord, such that:
  1. 1.
    Only one letter can be changed at a time
  2. 2.
    Each transformed word must exist in the word list. Note that beginWord is not a transformed word.
For example,
Given: beginWord="hit" endWord="cog" wordList=["hot","dot","dog","lot","log","cog"]
Return
1
[
2
["hit","hot","dot","dog","cog"],
3
["hit","hot","lot","log","cog"]
4
]
Copied!
Note:
  • Return an empty list if there is no such transformation sequence.
  • All words have the same length.
  • All words contain only lowercase alphabetic characters.
  • You may assume no duplicates in the word list.
  • You may assume beginWord and endWord are non-empty and are not the same.

2. Implementation

(1) BFS
1
class Solution {
2
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
3
if (wordList.size() == 0) {
4
return 0;
5
}
6
7
Set<String> dict = new HashSet<>();
8
9
for (String word : wordList) {
10
dict.add(word);
11
}
12
13
Queue<String> queue = new LinkedList<>();
14
queue.add(beginWord);
15
16
Set<String> visited = new HashSet<>();
17
visited.add(beginWord);
18
19
int len = 1;
20
21
while (!queue.isEmpty()) {
22
int size = queue.size();
23
24
for (int i = 0; i < size; i++) {
25
String curWord = queue.remove();
26
27
if (curWord.equals(endWord)) {
28
return len;
29
}
30
31
char[] letters = curWord.toCharArray();
32
for (int j = 0; j < curWord.length(); j++) {
33
char oldC = letters[j];
34
for (char c = 'a'; c <= 'z'; c++) {
35
letters[j] = c;
36
37
String nextWord = new String(letters);
38
39
if (dict.contains(nextWord) && !visited.contains(nextWord)) {
40
visited.add(nextWord);
41
queue.add(nextWord);
42
dict.remove(nextWord);
43
}
44
}
45
letters[j] = oldC;
46
}
47
}
48
++len;
49
}
50
return 0;
51
}
52
}
Copied!
(2) Bi-directional BFS
1
class Solution {
2
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
3
if (wordList.size() == 0) {
4
return 0;
5
}
6
7
Set<String> dict = new HashSet<>();
8
9
for (String word : wordList) {
10
dict.add(word);
11
}
12
13
if (!dict.contains(endWord)) {
14
return 0;
15
}
16
17
Set<String> visited = new HashSet<>();
18
Set<String> begin = new HashSet<>();
19
Set<String> end = new HashSet<>();
20
21
begin.add(beginWord);
22
end.add(endWord);
23
24
int len = 1;
25
26
while (!begin.isEmpty() && !end.isEmpty()) {
27
if (begin.size() > end.size()) {
28
Set<String> set = begin;
29
begin = end;
30
end = set;
31
}
32
33
Set<String> temp = new HashSet<>();
34
35
for (String word : begin) {
36
char[] letters = word.toCharArray();
37
38
for (int i = 0; i < letters.length; i++) {
39
char oldC = letters[i];
40
41
for (char c = 'a'; c <= 'z'; c++) {
42
letters[i] = c;
43
44
String nextWord = new String(letters);
45
46
if (end.contains(nextWord)) {
47
return len + 1;
48
}
49
50
51
if (dict.contains(nextWord) && !visited.contains(nextWord)) {
52
visited.add(nextWord);
53
temp.add(nextWord);
54
}
55
}
56
letters[i] = oldC;
57
}
58
}
59
++len;
60
begin = temp;
61
}
62
return 0;
63
}
64
}
Copied!

3. Time & Space Complexity

BFS: 时间复杂度:O(n * L * 26),其中n为word的个数,L为每个word的平均长度, 空间复杂度: O(n)