link1
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// import java.util.*;
class Solution {
public List<List<String>> findLadders(String start, String end, List<String> wordList) {
HashSet<String> wordSet = new HashSet<String>(wordList);
List<List<String>> res = new ArrayList<List<String>>();
HashMap<String, ArrayList<String>> nodeNeighbors = new HashMap<String, ArrayList<String>>();// Neighbors for
// every node
HashMap<String, Integer> distance = new HashMap<String, Integer>();// Distance of every node from the start node
ArrayList<String> solution = new ArrayList<String>();
wordSet.add(start);
bfs(start, end, wordSet, nodeNeighbors, distance);
dfs(start, end, wordSet, nodeNeighbors, distance, solution, res);
return res;
}
// BFS: Trace every node's distance from the start node (level by level).
private void bfs(String start, String end, Set<String> wordSet, HashMap<String, ArrayList<String>> nodeNeighbors,
HashMap<String, Integer> distance) {
for (String str : wordSet) nodeNeighbors.put(str, new ArrayList<String>());
Queue<String> queue = new LinkedList<String>();
queue.offer(start);
distance.put(start, 0);
while (!queue.isEmpty()) {
int count = queue.size();
boolean foundEnd = false;
for (int i = 0; i < count; i++) {
String cur = queue.poll();
int curDistance = distance.get(cur);
ArrayList<String> neighbors = getNeighbors(cur, wordSet);
for (String neighbor : neighbors) {
nodeNeighbors.get(cur).add(neighbor);
if (!distance.containsKey(neighbor)) {// Check if seen
distance.put(neighbor, curDistance + 1);
if (end.equals(neighbor))// Found the shortest path
foundEnd = true;
else
queue.offer(neighbor);
}
}
}
if (foundEnd) break;
}
}
// Find all next level nodes.
private ArrayList<String> getNeighbors(String node, Set<String> wordSet) {
ArrayList<String> res = new ArrayList<String>();
char chs[] = node.toCharArray();
for (char ch = 'a'; ch <= 'z'; ch++) {
for (int i = 0; i < chs.length; i++) {
if (chs[i] == ch) continue;
char old_ch = chs[i];
chs[i] = ch;
if (wordSet.contains(String.valueOf(chs))) {
res.add(String.valueOf(chs));
}
chs[i] = old_ch;
}
}
return res;
}
// DFS: output all paths with the shortest distance.
private void dfs(String cur, String end, Set<String> wordSet, HashMap<String, ArrayList<String>> nodeNeighbors,
HashMap<String, Integer> distance, ArrayList<String> solution, List<List<String>> res) {
solution.add(cur);
if (end.equals(cur)) {
res.add(new ArrayList<String>(solution));
} else {
for (String next : nodeNeighbors.get(cur)) {
if (distance.get(next) == distance.get(cur) + 1) {
dfs(next, end, wordSet, nodeNeighbors, distance, solution, res);
}
}
}
solution.remove(solution.size() - 1);
}
}
link
BFS + Path List1
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
64class Solution {
public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
List<List<String>> ans = new ArrayList<>();
if (!wordList.contains(endWord)) {// 如果不含有结束单词，直接结束，不然后边会造成死循环
return ans;
}
bfs(beginWord, endWord, new HashSet<>(wordList), ans);
return ans;
}
public void bfs(String beginWord, String endWord, Set<String> wordSet, List<List<String>> ans) {
Queue<List<String>> queue = new LinkedList<>();
List<String> path = new ArrayList<>();
Set<String> seen = new HashSet<>();
queue.offer(path);
path.add(beginWord);
seen.add(beginWord);
boolean isFound = false;
while (!queue.isEmpty()) {
int size = queue.size();
Set<String> subSeen = new HashSet<>(); // enable to traverse mutilple potential paths, see diagram bellow
for (int j = 0; j < size; j++) {
List<String> p = queue.poll();
String tmp = p.get(p.size() - 1);// 得到当前路径的末尾单词
ArrayList<String> neighbors = getNeighbors(tmp, wordSet); // 一次性得到所有的下一个的节点
for (String neighbor : neighbors) {
if (!seen.contains(neighbor)) { // 只考虑之前没有出现过的单词
if (neighbor.equals(endWord)) {// 到达结束单词
isFound = true;
p.add(neighbor);
ans.add(new ArrayList<String>(p));
p.remove(p.size() - 1);
}
p.add(neighbor);// 加入当前单词
queue.offer(new ArrayList<String>(p));
p.remove(p.size() - 1);
subSeen.add(neighbor);
}
}
}
seen.addAll(subSeen);
if (isFound) {
break;
}
}
}
private ArrayList<String> getNeighbors(String node, Set<String> wordSet) {
ArrayList<String> res = new ArrayList<String>();
char chs[] = node.toCharArray();
for (char ch = 'a'; ch <= 'z'; ch++) {
for (int i = 0; i < chs.length; i++) {
if (ch == chs[i]) continue;
char old_ch = chs[i];
chs[i] = ch;
if (wordSet.contains(String.valueOf(chs))) {
res.add(String.valueOf(chs));
}
chs[i] = old_ch;
}
}
return res;
}
}