Given two words ( start and end ), and a dictionary, find all transformation sequence(s) from start to end , such that:
- Only one letter can be changed at a time
- Each intermediate word must exist in the dictionary
Note:
- All words have the same length.
- All words contain only lowercase alphabetic characters.
尝试用Trie 来实现这个。
最后TLE（out of time）,不过算法已经正确了。
使用Trie，扩展性更好。 可以时时的加减dict里面的word， 也可以被多次调用。
1
package
leetcode;
2
3
import
java.util.ArrayList;
4
import
java.util.HashSet;
5
import
java.util.Iterator;
6
import
java.util.List;
7
import
java.util.Set;
8
9
//
implement wordLadder with Trie.
10
/*
11
* 如果这个函数要多次被调用，怎么办？
12
* 因为我每次都用挨个修改字母的办法来寻找新word，但如果能先对dictionary做个预处理，弄个从word到set of words之间的mapping，那么每轮BFS就可以省去寻找新词的时间。预处理字典的复杂度也是O(size of dictionary) * (length of string) * 26。最终可以用一个Hash<String, Set<String>>来表示这个mapping关系。
13
*
14
* 如果这个字典要增加/移除单词怎么办？
15
* 增加的话，只需要对新单词做同样的事情：修改每个字母找下一个单词，然后那个被找到下一个单词的mapping里同时也添加进新单词。因为这个关系是可互换的，如果wordA => wordB, 那么wordB => wordA。
16
* 删除的时候同理，对于map.get(toBeRemoved)里的所有单词的mapping集合都删掉这个toBeRemoved，然后再从map里面去掉它自己，写出来的代码大概是这样：
17
* for (String s : map.get(toBeRemoved)) map.get(s).remove(toBeRemoved);
18
* map.remove(toBeRemoved);
19
* 这个地方我一开始没注意到可以互换，以为还得预处理一个反方向的mapping，经过面试官两次提醒才发现了这个规律……
20
*
21
* 如果这个字典变得很庞大，这个mapping和字典本身就太占空间了，怎么处理？
22
* 用trie记录所有单词，每个node用一个bit记录这个node是否为一个单词，并且有一个set<myTrieNode>的field记录他可以变成的其他单词。至于如何构建这个field，利用trie的特性，可以用回溯的方法非常简单地找到可变过去的单词（在碰到公共ancestor之前，路径上的node个数必须相同，这个用于保证长度，并且至多只有一个字母不同，用于满足mapping的条件）
23
* 至此……时间终于用完了，问了下他的team的情况，就结束了……
24
*
25
*
*/
26
27
class
myTrieNode{
28
Boolean isWord;
29
myTrieNode[] childList;
30
Integer freq;
31
char
val;
32
String word;
33
34
public
myTrieNode(){
//
use to generate root of Trie
35
this
.freq = 0
;
36
this
.childList =
new
myTrieNode[26
];
37
this
.isWord =
false
;
38
}
39
40
public
myTrieNode(
char
c){
41
this
.val =
c;
42
this
.freq = 1
;
43
this
.childList =
new
myTrieNode[26
];
44
}
45
46
public
String containsWord(String s){
47
if
(s ==
null
|| s.length() == 0
){
48
if
(
this
.word !=
null
&&
this
.isWord ==
true
)
return
this
.word;
49
else
return
""
;
50
}
51
int
len =
s.length();
52
myTrieNode cur =
this
;
53
for
(
int
i = 0; i < len; i ++
){
54
char
c =
s.charAt(i);
55
if
(cur.childList[c - 'a'] !=
null
){
56
cur = cur.childList[c - 'a'
];
57
}
else
{
58
return
null
;
59
}
60
}
61
return
cur.isWord ==
true
? cur.word :
null
;
62
}
63
}
64
class
myTrie{
65
myTrieNode root;
66
67
public
myTrie(){
68
this
.root =
new
myTrieNode();
69
}
70
71
public
void
insert(String word){
72
if
(word ==
null
|| word.length() == 0)
return
;
73
int
len =
word.length();
74
myTrieNode cur =
this
.root;
75
for
(
int
i = 0; i < len; i ++
){
76
char
c =
word.charAt(i);
77
if
(cur.childList[c - 'a'] ==
null
){
78
cur.childList[c - 'a'] =
new
myTrieNode(c);
79
}
else
{
80
cur.childList[c - 'a'].freq ++
;
81
}
82
cur = cur.childList[c - 'a'
];
83
if
(i == word.length() - 1
){
84
cur.isWord =
true
;
85
cur.word =
word;
86
}
87
}
88
}
89
90
}
91
public
class
WordLadder {
92
93
94
private
static
myTrie trie;
95
private
static
List<List<String>>
result;
96
public
static
List<List<String>> findLadders(String start, String end, Set<String>
dict) {
97
trie =
generateTrie(dict);
98
trie.insert(end);
99
result =
new
ArrayList<List<String>>
();
100
ArrayList<String> row =
new
ArrayList<String>
();
101
row.add(start);
102
findLadderSequence(start, end, row,
new
HashSet<String>
());
103
return
result;
104
}
105
106
private
static
void
findLadderSequence(String start, String end, ArrayList<String> row, HashSet<String>
usedSet){
107
if
(start.equals(end)){
108
result.add(row);
109
}
110
myTrieNode cur =
trie.root;
111
myTrieNode next =
cur;
112
for
(
int
i = 0; i < start.length(); i ++
){
113
char
c =
start.charAt(i);
114
for
(
int
j = 0; j < 26; j ++
){
115
if
(cur.childList[j] !=
null
&& cur.childList[j].val ==
c){
116
next =
cur.childList[j];
117
}
118
if
(cur.childList[j] !=
null
&& cur.childList[j].val !=
c){
119
String tmp = cur.childList[j].containsWord(start.substring(i + 1
));
120
if
(tmp !=
null
&& !
usedSet.contains(tmp)){
121
row.add(tmp);
122
usedSet.add(tmp);
123
findLadderSequence(tmp, end,
new
ArrayList<String>(row),
new
HashSet<String>
(usedSet));
124
row.remove(row.size() - 1
);
125
usedSet.remove(tmp);
126
}
127
}
128
}
129
cur =
next;
130
}
131
132
}
133
134
private
static
myTrie generateTrie(Set<String>
dict){
135
myTrie trie =
new
myTrie();
136
if
(dict.isEmpty())
return
trie;
137
//
generate Trie for dictionary
138
Iterator it =
dict.iterator();
139
while
(it.hasNext()){
140
String word =
(String)it.next();
141
trie.insert(word);
142
}
143
return
trie;
144
}
145
146
public
static
void
main(String[] args){
147
String start = "hit"
;
148
String end = "cog"
;
149
Set<String> dict =
new
HashSet<String>
();
150
dict.add("hot"
);
151
dict.add("dot"
);
152
dict.add("dog"
);
153
dict.add("lot"
);
154
dict.add("log"
);
155
findLadders(start, end, dict);
156
System.out.println(result);
157
}
158
}
Output:
[[hit, hot, dot, lot, log, cog],
[hit, hot, dot, lot, log, dog, cog],
[hit, hot, dot, dog, cog],
[hit, hot, dot, dog, log, cog],
[hit, hot, lot, dot, dog, cog],
[hit, hot, lot, dot, dog, log, cog],
[hit, hot, lot, log, cog],
[hit, hot, lot, log, dog, cog]]
