#Problem

Word Ladder II

#Solution

#Solution #1 BFS + backtracking without optimization

简单粗暴的方法还是比较容易想, 分两步:

  1. 先利用BFS做Word Ladder I 的事情, 计算出最短的距离. 一边计算一边构建一个undirected graph, 包含start to end的所有可能路径.
  2. 然后利用DFS做搜索, 并且维护一个depth, 没往下走一步depth加一, 如果depth已经到达了最短的距离, 但所在节点并不是endWord的话, 就回溯找其他路. 总有一条path, 从start to end的长度为第一步所求到的最短距离.

很遗憾. 这个方法超时了.

#Solution #2 BFS + DFS with Optimization

优化的方法是在第一步BFS的过程中, 利用一个hash map记录start到每一个结点的最短距离.

那么在第二步DFS的过程中, 我们就不需要一个一个的尝试, 不行了还得回溯. 我们可以利用那个distance的hash map, 在继续往下之前, check下一个结点的最短距离是否是当前结点最短距离加一. 是的话就继续, 不是的话就根本不需要visit那个结点了.

#Code

#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
// https://leetcode.com/problems/word-ladder-ii/discuss/40475/My-concise-JAVA-solution-based-on-BFS-and-DFS
class Solution {
public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
final List<List<String>> res = new ArrayList<>();
final Set<String> dict = new HashSet<>(wordList);
if (!dict.contains(endWord)) return res;
final Map<String, Set<String>> graph = new HashMap<>();
final Map<String, Integer> dist = new HashMap<>();
bfs(beginWord, endWord, dict, graph, dist);
if (!dist.containsKey(endWord) || dist.get(endWord) == 0) return res;
final List<String> list = new ArrayList<>(Arrays.asList(beginWord));
dfs(beginWord, endWord, graph, dist, res, list);
return res;
}
private void bfs(final String beginWord, final String endWord, final Set<String> dict,
final Map<String, Set<String>> graph, final Map<String, Integer> dist) {
final Queue<String> queue = new LinkedList<>();
queue.add(beginWord);
dist.put(beginWord, 1);
int depth = 0;
while (!queue.isEmpty()) {
final int size = queue.size();
depth++;
for (int i = 0; i < size; i++) {
final String curr = queue.poll();
graph.put(curr, new HashSet<>());
if (curr.equals(endWord)) return;
final char[] chs = curr.toCharArray();
for (int k = 0; k < chs.length; k++) {
final char save = chs[k];
for (char c = 'a'; c <= 'z'; c++) {
if (c != save) {
chs[k] = c;
final String nextWord = new String(chs);
if (dict.contains(nextWord)) {
graph.putIfAbsent(nextWord, new HashSet<>());
graph.get(curr).add(nextWord);
if (!dist.containsKey(nextWord)) {
dist.put(nextWord, depth + 1);
queue.add(nextWord);
}
}
chs[k] = save;
}
}
}
}
}
}
private void dfs(final String beginWord, final String endWord, final Map<String, Set<String>> graph, final Map<String, Integer> dist,
final List<List<String>> res, final List<String> list) {
if (beginWord.equals(endWord)) {
res.add(new ArrayList<>(list));
return;
}
final int len = dist.get(beginWord);
for (final String adj : graph.get(beginWord)) {
if (dist.get(adj) == len + 1) {
list.add(adj);
dfs(adj, endWord, graph, dist, res, list);
list.remove(list.size() - 1);
}
}
}
}

Comments