-
Notifications
You must be signed in to change notification settings - Fork 0
/
126.java
88 lines (85 loc) · 3.04 KB
/
126.java
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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
//https://leetcode.com/problems/word-ladder-ii/
public class Solution {
boolean connect(String a, String b) {
int diff = 0;
for(int i =0; i< a.length(); ++i) {
if(a.charAt(i) != b.charAt(i)) {
diff++;
if(diff > 1) return false;
}
}
return diff == 1;
}
static class Node {
String word;
int dist;
public Node(String w, int d) {
word = w;
dist = d;
}
}
void findPath(Node cur, String sw, List<String> path, List<List<String>> ret, Map<String, List<Node>> pa) {
if(cur.word.equals(sw)) {
path.add(sw);
Collections.reverse(path);
ret.add(path);
return;
}
for(Node pre : pa.get(cur.word)) {
List<String> np = new ArrayList<>(path);
np.add(cur.word);
findPath(pre, sw, np, ret, pa);
}
}
public List<List<String>> findLadders(String bw, String ew, List<String> wordList) {
if(wordList == null || wordList.size() == 0 ) return new ArrayList<>();
List<List<String>> ret = new ArrayList<>();
Map<String, Integer> table = new HashMap<>();
Map<String, List<Node>> parents = new HashMap<>();
PriorityQueue<Node> pq = new PriorityQueue<Node>((n1, n2) -> n1.dist - n2.dist);
Node source = new Node(bw, 0);
for(String w: wordList) {
if(connect(w, bw)) {
table.put(w, 1);
Node n = new Node(w, 1);
pq.add(n);
List<Node> ns = new ArrayList<>();
ns.add(source);
parents.put(w, ns);
} else {
table.put(w, Integer.MAX_VALUE);
}
}
while(!pq.isEmpty()) {
Node cur = pq.poll();
if(cur.word.equals(ew)) {
findPath(cur, bw, new ArrayList<>(), ret, parents);
return ret;
}
if(cur.dist > table.get(cur.word)) continue;
char[] chs = cur.word.toCharArray();
for(int i = 0; i < chs.length; ++i) {
char orig = chs[i];
for(int to = 'a'; to <= 'z'; ++to) {
if(orig == to) continue;
chs[i] = (char)to;
String chw = new String(chs);
if(table.containsKey(chw)) {
int oldV = table.get(chw);
if( oldV > cur.dist + 1) {
table.put(chw, cur.dist + 1);
pq.add(new Node(chw, cur.dist + 1));
List<Node> ns = new ArrayList<>();
ns.add(cur);
parents.put(chw, ns);
} else if (oldV == cur.dist + 1) {
parents.get(chw).add(cur);
}
}
}
chs[i] = orig;
}
}
return ret;
}
}