feat: $212

robot · robot · commit b724e44bfd71 · 2021-09-16T15:30:08.000+08:00
diff --git a/README.md b/README.md
@@ -466,7 +466,7 @@ leetcode 题解，记录自己的 leetcode 解题之路。
 - [0145. 二叉树的后序遍历](./problems/145.binary-tree-postorder-traversal.md)
 - [0146. LRU 缓存机制](./problems/146.lru-cache.md)
 - [0154. 寻找旋转排序数组中的最小值 II](./problems/154.find-minimum-in-rotated-sorted-array-ii.md)
-<!-- - [0212. 单词搜索 II](./problems/212.word-search-ii.md) -->
+- [0212. 单词搜索 II](./problems/212.word-search-ii.md)
 - [0239. 滑动窗口最大值](./problems/239.sliding-window-maximum.md) 👍
 - [0295. 数据流的中位数](./problems/295.find-median-from-data-stream.md)
 - [0297. 二叉树的序列化与反序列化](./problems/297.serialize-and-deserialize-binary-tree.md) 91
diff --git a/SUMMARY.md b/SUMMARY.md
@@ -288,7 +288,7 @@
   - [0145. 二叉树的后序遍历](./problems/145.binary-tree-postorder-traversal.md)
   - [0146. LRU 缓存机制](./problems/146.lru-cache.md)
   - [0154. 寻找旋转排序数组中的最小值 II](./problems/154.find-minimum-in-rotated-sorted-array-ii.md)
-  <!-- - [0212. 单词搜索 II](./problems/212.word-search-ii.md) -->
+  - [0212. 单词搜索 II](./problems/212.word-search-ii.md)
   - [0239. 滑动窗口最大值](./problems/239.sliding-window-maximum.md)
   - [0295. 数据流的中位数](./problems/295.find-median-from-data-stream.md)
   - [0297. 二叉树的序列化与反序列化](./problems/297.serialize-and-deserialize-binary-tree.md) 91
diff --git a/problems/212.word-search-ii.md b/problems/212.word-search-ii.md
@@ -62,8 +62,12 @@ words = ["oath","pea","eat","rain"] and board =
 
 刚才我提到了一个关键词“前缀”，我们考虑使用前缀树来优化。使得复杂度降低为$O(h)$, 其中 h 是前缀树深度，也就是最长的字符串长度。
 
+关于前缀树，可以参考我的[前缀树](../thinkings/trie.md) 专题。
+
 ![](https://tva1.sinaimg.cn/large/007S8ZIlly1ghlua4m3ofj30mz0gqdhc.jpg)
 
+值得注意的是如果每次 dfs 都使用 startsWith 来判断，那么会超时。我们可以将当前遍历到的 trie 节点 以参数传递到 dfs 中，这样可以进一步减少复杂度。
+
 ## 关键点
 
 - 前缀树（也叫字典树），英文名 Trie（读作 tree 或者 try）
@@ -79,77 +83,46 @@ Python3 Code：
 关于 Trie 的代码:
 
 ```python
+from collections import defaultdict
 class Trie:
-
     def __init__(self):
-        """
-        Initialize your data structure here.
-        """
-        self.Trie = {}
+        self.children = defaultdict(Trie)
+        self.word = ""
 
     def insert(self, word):
-        """
-        Inserts a word into the trie.
-        :type word: str
-        :rtype: void
-        """
-        curr = self.Trie
-        for w in word:
-            if w not in curr:
-                curr[w] = {}
-            curr = curr[w]
-        curr['#'] = 1
-
-    def startsWith(self, prefix):
-        """
-        Returns if there is any word in the trie that starts with the given prefix.
-        :type prefix: str
-        :rtype: bool
-        """
-
-        curr = self.Trie
-        for w in prefix:
-            if w not in curr:
-                return False
-            curr = curr[w]
-        return True
+        cur = self
+        for c in word:
+            cur = cur.children[c]
+        cur.word = word
 ```
 
 主逻辑代码：
 
 ```python
+
 class Solution:
     def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
-        m = len(board)
-        if m == 0:
-            return []
-        n = len(board[0])
+        def dfs(row, col, cur):
+            if row < 0 or row >= m or col < 0 or col >= n or board[row][col] == '.' or board[row][col] not in cur.children: return
+            c = board[row][col]
+            cur  = cur.children[c]
+            if cur.word != '': ans.add(cur.word)
+            board[row][col] = '.'
+            dfs(row+1,col, cur)
+            dfs(row-1,col, cur)
+            dfs(row,col+1, cur)
+            dfs(row,col-1, cur)
+            board[row][col] = c
+        m, n = len(board), len(board[0])
+        ans = set()
         trie = Trie()
-        seen = None
-        res = set()
+        words = set(words)
         for word in words:
             trie.insert(word)
-
-        def dfs(s, i, j):
-            if (i, j) in seen or i < 0 or i >= m or j < 0 or j >= n or not trie.startsWith(s):
-                return
-            s += board[i][j]
-            seen[(i, j)] = True
-
-            if s in words:
-                res.add(s)
-            dfs(s, i + 1, j)
-            dfs(s, i - 1, j)
-            dfs(s, i, j + 1)
-            dfs(s, i, j - 1)
-
-            del seen[(i, j)]
-
         for i in range(m):
             for j in range(n):
-                seen = dict()
-                dfs("", i, j)
-        return list(res)
+                dfs(i, j, trie)
+        return list(ans)
 ```
 
 ## 相关题目
diff --git a/thinkings/trie.md b/thinkings/trie.md
@@ -1,4 +1,4 @@
-# Trie（来自公众号力扣加加的活动《91天学算法》的讲义）
+# Trie（来自公众号力扣加加的活动《91 天学算法》的讲义）
 
 ## 简介
 
@@ -225,3 +225,32 @@ class Trie:
 最后给大家提供了两种语言的前缀树模板，大家如果需要用，直接将其封装成标准 API 调用即可。
 
 基于前缀树的题目变化通常不大， 使用模板就可以解决。如何知道该使用前缀树优化是一个难点，不过大家只要牢牢记一点即可，那就是**算法的复杂度瓶颈在字符串查找，并且字符串有很多公共前缀，就可以用前缀树优化**。
+
+## 扩展
+
+还有一种建树方法，我们简单介绍一下。
+
+我们可以用递归的方式来建树，每一个节点称为 TrieNode。
+
+TrieNode 接口如下：
+
+```py
+children: TrieNode[] # 子节点
+word: string # 当前节点结尾的单词
+```
+
+```py
+from collections import defaultdict
+class Trie:
+    def __init__(self):
+        self.children = defaultdict(Trie)
+        self.word = ""
+
+    def insert(self, word):
+        cur = self
+        for c in word:
+            cur = cur.children[c]
+        cur.word = word
+```
+
+这种方法在某些题目中比较有用，比如 [212. 单词搜索 II](https://github.com/azl397985856/leetcode/blob/master/problems/212.word-search-ii.md)。
