四刷 06/2022
首先搞懂了为什么要BFS+DFS，因为BFS没有办法记录路径
在第一遍BFS的时候用HashSet记录了每个点的previous node，这里有情况就是上一层有可能同时有两个parent都指向当前node,同时也有可能当前层有邻居node指向当前node
如果是邻居node指向当前node就不满足shortest path的需求
我的解决办法是每一个layer traverse的时候新建一个hashmap，而检查是否visited的时候只检查之前的hashmap，这样保证了两个parent node pop出来的当前node都可以被记录下来，最后当前层结束之后再把层map加入到最终的previous map里面
Time O(N*K^2) -> N is the number of nodes, traverse the graph with BFS will use O(N) time
K is the word length. While traversing each node, we take O(26 K) time to replace each character of the word and use O(K) time to generate the string to check from the hashset, so that's O(N* K^2)
The backward dfs traverse won't take more than O(N) time
Space O(NK) for the set to store the words and the queue for BFS
Runtime: 17 ms, faster than 61.93% of Java online submissions for Word Ladder II.
Memory Usage: 43.4 MB, less than 76.61% of Java online submissions for Word Ladder II.
class Solution {
public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
// Do a level order traversal from beginWord to endWord
// Use a map to keep track of each word's previous word in the graph
// Once we found the endWord, we search backwards using the previous pointer and record the path
Set<String> wordSet = new HashSet<>(wordList);
// prev is also used as visited map
Map<String, Set<String>> prev = new HashMap<>();
Queue<String> que = new ArrayDeque<>();
que.offer(beginWord);
boolean found = false;
List<List<String>> result = new ArrayList<>();
while (!que.isEmpty() && !found) {
int size = que.size();
Map<String, Set<String>> temp = new HashMap<>();
while (size-- > 0) {
String curr = que.poll();
for (String next : neighbors(curr, wordSet)) {
// System.out.printf("curr:%s,next:%s,prevMap:%s\n", curr, next, prev.toString());
if (prev.containsKey(next)) {
continue;
}
if (next.equals(endWord)) {
found = true;
}
temp.putIfAbsent(next, new HashSet<>());
temp.get(next).add(curr);
que.offer(next);
}
}
prev.putAll(temp);
}
dfs(prev, beginWord, result, new LinkedList<>(), endWord);
return result;
}
private void dfs(Map<String, Set<String>> map, String beginWord, List<List<String>> result, List<String> path, String word) {
path.add(0, word);
if (word.equals(beginWord)) {
result.add(new ArrayList<>(path));
path.remove(0);
return;
}
for (String prev : map.getOrDefault(word, new HashSet<>())) {
dfs(map, beginWord, result, path, prev);
}
path.remove(0);
}
private List<String> neighbors(String word, Set<String> wordSet) {
// replace each character of the word and check if that new word is in the word set
List<String> result = new ArrayList<>();
char[] chars = word.toCharArray();
for (int i = 0; i < chars.length; i++) {
char originalChar = chars[i];
for (char c = 'a'; c <= 'z'; c++) {
if (c == originalChar) {
continue;
}
chars[i] = c;
String nWord = new String(chars);
if (wordSet.contains(nWord)) {
result.add(nWord);
}
}
chars[i] = originalChar;
}
// System.out.printf("from:%s, to:%s\n", word, result.toString());
return result;
}
}
基本上是 build + BFS + DFS 一遍写出来的，写了大概40分钟
三个bug
1没有把 beginWord加入到wordList和words set里面，导致graph里面没有beginWord
2写BFS的时候考虑到了可能无法走到endword的情况并且返回null，但是main method里面忘记check了。。。 org
导致了一个NullPointerException
3DFS里面的neighbor有可能虽然是当前node的neighbor，但是无法从beginword到达
想了一下为什么会有这个情况
因为BFS为了优化，在到达endWord之后就停止了，这样所有比endWord距离更远的点都没有加入到map里面
这样会导致比endWord远的connected component没有值
所以需要特殊check一下
我这里用的Integer.equals() 来包含了Null的情况
54.86 %
class Solution {
public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
// build graph
// two words can be connected if they only have 1 diff character
// start bfs from start to end and generate shorted steps from start to all nodes
// dfs from end to start, each time only step into node that are 1 step nearer to start
List<List<String>> result = new ArrayList<>();
wordList.add(beginWord);
Set<String> words = new HashSet<>(wordList);
if (!words.contains(endWord)) return result;
Map<String, Set<String>> graph = buildGraph(wordList, words);
Map<String, Integer> map = getSP(beginWord, endWord, graph); // shortest path from beginWord
if (map == null) return result;
List<String> path = new LinkedList<>();
path.add(endWord);
dfs(endWord, beginWord, endWord, graph, map, path, result);
return result;
}
private void dfs(String word, String beginWord, String endWord, Map<String, Set<String>> graph, Map<String, Integer> map, List<String> path, List<List<String>> result) {
// System.out.println(word);
if (word.equals(beginWord)) {
result.add(new ArrayList<>(path));
return;
}
Integer dist = map.get(word) - 1;
// given a word, trying to reach beginWord
Set<String> neighbors = graph.get(word);
for (String neighbor : neighbors) {
if (dist.equals(map.get(neighbor))) { // in case thie neighbor can't be reached by beginWord
path.add(0, neighbor);
dfs(neighbor, beginWord, endWord, graph, map, path, result);
path.remove(neighbor);
}
}
}
private Map<String, Integer> getSP(String beginWord, String endWord, Map<String, Set<String>> graph) {
Map<String, Integer> map = new HashMap<>(); // shortest path from beginWord
Queue<String> que = new LinkedList<>();
Set<String> visited = new HashSet<>();
visited.add(beginWord);
que.offer(beginWord);
int step = 0;
while (!que.isEmpty()) {
int size = que.size();
while (size-- > 0) {
String curr = que.poll();
// System.out.println(curr + " step " + step);
map.put(curr, step);
if (curr.equals(endWord)) return map;
Set<String> neighbors = graph.get(curr);
for (String neighbor : neighbors) {
if (visited.add(neighbor)) {
que.offer(neighbor);
}
}
}
step++;
}
return null;
}
private Map<String, Set<String>> buildGraph(List<String> wordList, Set<String> words) {
Map<String, Set<String>> graph = new HashMap<>();
for (String word : wordList) {
Set<String> neighbors = new HashSet<>();
char[] chars = word.toCharArray();
for (int i = 0; i < chars.length; i++) {
char c = chars[i];
for (char t = 'a'; t <= 'z'; t++) {
if (t != c) {
chars[i] = t;
String str = new String(chars);
if (words.contains(str)) {
neighbors.add(str);
}
}
}
chars[i] = c;
}
graph.put(word, neighbors);
}
return graph;
}
}
二刷 9/17
（看了一下一刷的答案，感觉像傻逼一样啊，第一遍bfs记录的是每个点和start点的距离？九章老师当时讲的时候是不是脑子瓦特了）
写了一个5 + 25 + 25 + 10 mins
总的来说感觉思路很清楚
bug1 忘记了把Neighbors加入到queue里面
bug2 在buildGraph里面判断能不能最终走到endPoint。一开始判断没有endPoint的条件是graph.size() == 0，有错。想了一下发现因为graph是一边走一边build的，所以即使没有找到也是有size的，应该在buildGraph最后return之前看一下boolean found，如果没有found就直接返回null
我自己感觉难点在于level order traversal的时候
如果在一层遇到了一个点，不能立刻把它从set里面去掉，因为上一层的其他点也可能访问到它，所以应该先全部暂时用一个set存下来，这一层结束后才能统一从wordSet里面去掉。因为如果之后层再访问就不是最短路径了
85.73 %
class Solution {
public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
List<List<String>> result = new ArrayList<>();
if (beginWord == null || endWord == null) return result;
// bfs to find the shortest path and construct the graph
// key-String of word, value-List<String>-neighbors of its previous layer
Map<String, List<String>> graph = buildGraph(beginWord, endWord, wordList); //TODO
if (graph != null && graph.size() != 0) {
// start from endWord, do dfs search until reach the beginWord point, keep track of paths
findPath(beginWord, endWord, graph, new ArrayList<>(), result);
}
return result;
}
private Map<String, List<String>> buildGraph(String beginWord, String endWord, List<String> wordList) {
Map<String, List<String>> graph = new HashMap<>();
Queue<String> que = new LinkedList<>();
// Convert wordList into wordSet, to reduce time complexity
Set<String> wordSet = new HashSet<>();
for (String word : wordList) wordSet.add(word);
que.offer(beginWord);
boolean found = false;
while (!que.isEmpty() && wordSet.size() != 0 && !found) {
int size = que.size();
Set<String> visited = new HashSet<>();
// travel level by level
while (size-- > 0) {
String curr = que.poll();
char[] chars = curr.toCharArray();
// getNeighbors
for (char newChar = 'a'; newChar <= 'z'; newChar++) {
for (int i = 0; i < curr.length(); i++) {
if (newChar != chars[i]) {
char oldChar = chars[i];
chars[i] = newChar;
String newWord = new String(chars);
if (wordSet.contains(newWord)) {
if (!graph.containsKey(newWord)) graph.put(newWord, new ArrayList<>());
graph.get(newWord).add(curr);
if (!visited.contains(newWord)) {
visited.add(newWord);
que.offer(newWord);
}
}
// Set back
chars[i] = oldChar;
}
}
}
}
// delete this layer from wordList
for (String s : visited) {
wordSet.remove(s);
if (s.equals(endWord)) found = true;
}
}
if (found) return graph;
else return null;
}
private void findPath(String beginWord, String currWord, Map<String, List<String>> graph, List<String> path, List<List<String>> result) {
path.add(currWord);
if (currWord.equals(beginWord)) {
List<String> subResult = new ArrayList<>();
for (int i = path.size() - 1; i >= 0; i--) {
subResult.add(path.get(i));
}
result.add(subResult);
} else {
List<String> prevNeighbors = graph.get(currWord);
for (String prevNeighbor : prevNeighbors) {
findPath(beginWord, prevNeighbor, graph, path, result);
}
}
path.remove(path.size() - 1);
}
}
一刷
LintCode Version
这道题在知道思路的情况下还是用了3个多小时才写出来，耗时很长。
整体思路是先用bfs从end点找到start点， 得到一个中间点到end距离的HashMap。
然后从start点进行dfs，每次都只对距离有所缩短的点进行搜索，防止进行无用的搜索，大大节省了运行时间。
主要有这样几个bug：
1. HashMap<String, int> 这种写法是错误的， HashMap里面不能有primitive type。要写成HashMap<String, Integer>
2. 有一个地方两个String的比较写成了“==”， 这样属于比较了两个String的reference, 而不是值相等。这里要求的是值相等，所以必须写成“string1.equals(string2)”的形式
3. 默认start和end是不包含在dictionary里面的。刚开始写的时候只考虑到要把end加入到dict里面。但是在bfs运行中，从end点搜索到start点，此时如果start点不在dict里面，就不会被作为任何点的neighbor，造成distance的HashMap里面start点的value是null。而dfs调用distance.get(start)的时候就会报NullPointerException。所以必须在初始时将start和end都加入到dict里面。
public class Solution {
/**
* @param start, a string
* @param end, a string
* @param dict, a set of string
* @return a list of lists of string
*/
public List<List<String>> findLadders(String start, String end, Set<String> dict) {
// write your code here
List<List<String>> result = new ArrayList<>();
if (start.equals(end)) {
List<String> temp = new ArrayList<>();
temp.add(start);
result.add(temp);
return result;
}
if (dict == null) {
return result;
}
dict.add(start);
dict.add(end);
//A bfs function which returns a hashmap
//k - string of the word
//value - distance to the end word
Map<String, Integer> distance = bfs(start, end, dict);
//call the dfs function recursively
//add paths to result
List<String> path = new ArrayList<>();
path.add(start);
dfs(end, start, path, result, dict, distance);
return result;
}
public void dfs(String end, String word, List<String> path,
List<List<String>> result, Set<String> dict,
Map<String, Integer> distance) {
if (word.equals(end)) {
result.add(new ArrayList<String>(path));
return;
}
List<String> neighbors = getNeighbors(word, dict);
//System.out.println(neighbors);
for (String neighbor : neighbors) {
//System.out.println(word + " " + neighbor + " " + distance.get(word) + " " + distance.get(neighbor));
if (distance.get(word) == distance.get(neighbor) + 1) {
path.add(neighbor);
//System.out.println("path " + path);
dfs(end, neighbor, path, result, dict, distance);
path.remove(path.size() - 1);
}
}
}
public Map<String, Integer> bfs(String start, String end, Set<String> dict) {
Map<String, Integer> distance = new HashMap<String, Integer>();
for (String word : dict) {
distance.put(word, Integer.MAX_VALUE);
}
Queue<String> que = new LinkedList<>();
Set<String> visited = new HashSet<>();
que.offer(end);
visited.add(end);
int length = 1;
distance.put(end, length);
while(!que.isEmpty()) {
int size = que.size();
length++;
for (int i = 0; i < size; i++) {
String curr = que.poll();
List<String> neighbors = getNeighbors(curr, dict);
for (String neighbor : neighbors) {
if (neighbor.equals(start)) {
//System.out.println("start: " + neighbor);
distance.put(neighbor, length);
//System.out.println("length: " + distance.get(start));
return distance;
}
if (visited.contains(neighbor) || que.contains(neighbor)) {
continue;
}
distance.put(neighbor, length);
visited.add(neighbor);
que.offer(neighbor);
}
}
}
return distance;
}
public List<String> getNeighbors(String word, Set<String> dict) {
List<String> neighbors = new ArrayList<>();
for (int k = 0; k < word.length(); k++) {
for (char c = 'a'; c <= 'z'; c++) {
if (c == word.charAt(k)) {
continue;
}
String newWord = word.substring(0, k) + c + word.substring(k + 1);
if (dict.contains(newWord)) {
neighbors.add(newWord);
}
}
}
return neighbors;
}
}
No comments:
Post a Comment