提交第7期作业

ryuhi · ryuhi · commit 26097867a7f6 · 2020-07-27T02:34:03.000+08:00
diff --git a/Week07/LadderLength.java b/Week07/LadderLength.java
@@ -0,0 +1,45 @@
+import java.util.*;
+
+public class LadderLength {
+
+    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
+        HashSet<String> start = new HashSet<>();
+        start.add(beginWord);
+        HashSet<String> end = new HashSet<>();
+        end.add(endWord);
+        HashSet<String> words = new HashSet<>(wordList);
+        if (!words.contains(endWord)) {
+            return 0;
+        }
+        return deBfs(start,end,words,2);
+    }
+    private int deBfs(HashSet<String> start, HashSet<String> end, HashSet<String> words, int depth) {
+        if (start.size() > end.size()) {
+            return deBfs(end, start, words, depth);
+        }
+        words.removeAll(start);
+        HashSet<String> next = new HashSet<>();
+        for (String str : start) {
+            char[] chars = str.toCharArray();
+            for (int i = 0; i < chars.length; i++) {
+                char temp = chars[i];
+                for (char j = 'a'; j <= 'z'; j++) {
+                    chars[i] = j;
+                    String word = new String(chars);
+                    if (words.contains(word)) {
+                        if (end.contains(word)) {
+                            return depth;
+                        }
+                        next.add(word);
+                    }
+                }
+                chars[i] = temp;
+            }
+
+        }
+        if (start.isEmpty()) {
+            return 0;
+        }
+        return deBfs(next, end, words, depth + 1);
+    }
+}
diff --git a/Week07/NOTE.md b/Week07/NOTE.md
@@ -1 +1,26 @@
-学习笔记
+学习笔记
+
+```python
+def doubleBFS(graph, start, end):
+    visited = set()
+	startQueue = [] 
+	startQueue.append([start]) 
+	while startQueue: 
+		node = startQueue.pop() 
+		visited.add(node)
+		process(node) 
+		nodes = generate_related_nodes(node) 
+		startQueue.push(nodes)
+	# other processing work 
+  	endQueue = [] 
+	endQueue.append([end]) 
+	while endQueue: 
+		node = endQueue.pop() 
+		visited.add(node)
+		process(node) 
+		nodes = generate_related_nodes(node) 
+		endQueue.push(nodes)
+	# other processing work 
+    retainall(startQueue, endQueue)
+```
+
diff --git a/Week07/Trie.java b/Week07/Trie.java
@@ -0,0 +1,49 @@
+public class Trie {
+
+    private boolean isEnd;
+    private Trie[] next;
+    /** Initialize your data structure here. */
+    public Trie() {
+        isEnd = false;
+        next = new Trie[26];
+    }
+
+    /** Inserts a word into the trie. */
+    public void insert(String word) {
+        if (word == null || word.length() == 0) {
+            return;
+        }
+        Trie curr = this;
+        char[] words = word.toCharArray();
+        for (int i = 0;i < words.length;i++) {
+            int n = words[i] - 'a';
+            if (curr.next[n] == null) {
+                curr.next[n] = new Trie();
+            }
+            curr = curr.next[n];
+        }
+        curr.isEnd = true;
+    }
+
+    /** Returns if the word is in the trie. */
+    public boolean search(String word) {
+        Trie node = searchPrefix(word);
+        return node != null && node.isEnd;
+    }
+
+    /** Returns if there is any word in the trie that starts with the given prefix. */
+    public boolean startsWith(String prefix) {
+        Trie node = searchPrefix(prefix);
+        return node != null;
+    }
+
+    private Trie searchPrefix(String word) {
+        Trie node = this;
+        char[] words = word.toCharArray();
+        for (int i = 0;i < words.length;i++) {
+            node = node.next[words[i] - 'a'];
+            if (node == null) return null;
+        }
+        return node;
+    }
+}
