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 來實現(xiàn)這個。
最后TLE（out of time）,不過算法已經(jīng)正確了。?
使用Trie，擴展性更好。 可以時時的加減dict里面的word， 也可以被多次調(diào)用。
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
* 如果這個函數(shù)要多次被調(diào)用，怎么辦？
12
* 因為我每次都用挨個修改字母的辦法來尋找新word，但如果能先對dictionary做個預(yù)處理，弄個從word到set of words之間的mapping，那么每輪BFS就可以省去尋找新詞的時間。預(yù)處理字典的復(fù)雜度也是O(size of dictionary) * (length of string) * 26。最終可以用一個Hash<String, Set<String>>來表示這個mapping關(guān)系。
13
*
14
* 如果這個字典要增加/移除單詞怎么辦？
15
* 增加的話，只需要對新單詞做同樣的事情：修改每個字母找下一個單詞，然后那個被找到下一個單詞的mapping里同時也添加進新單詞。因為這個關(guān)系是可互換的，如果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
* 這個地方我一開始沒注意到可以互換，以為還得預(yù)處理一個反方向的mapping，經(jīng)過面試官兩次提醒才發(fā)現(xiàn)了這個規(guī)律……
20
*
21
* 如果這個字典變得很龐大，這個mapping和字典本身就太占空間了，怎么處理？
22
* 用trie記錄所有單詞，每個node用一個bit記錄這個node是否為一個單詞，并且有一個set<myTrieNode>的field記錄他可以變成的其他單詞。至于如何構(gòu)建這個field，利用trie的特性，可以用回溯的方法非常簡單地找到可變過去的單詞（在碰到公共ancestor之前，路徑上的node個數(shù)必須相同，這個用于保證長度，并且至多只有一個字母不同，用于滿足mapping的條件）
23
* 至此……時間終于用完了，問了下他的team的情況，就結(jié)束了……
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]]
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯(lián)系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
