# 0212. 單詞搜索 II ## 題目地址（212. 單詞搜索 II） <https://leetcode-cn.com/problems/word-search-ii/> ## 題目描述 ``` <pre class="calibre18">``` 給定一個二維網格 board 和一個字典中的單詞列表 words，找出所有同時在二維網格和字典中出現的單詞。 單詞必須按照字母順序，通過相鄰的單元格內的字母構成，其中“相鄰”單元格是那些水平相鄰或垂直相鄰的單元格。同一個單元格內的字母在一個單詞中不允許被重復使用。 示例: 輸入: words = ["oath","pea","eat","rain"] and board = [ ['o','a','a','n'], ['e','t','a','e'], ['i','h','k','r'], ['i','f','l','v'] ] 輸出: ["eat","oath"] 說明: 你可以假設所有輸入都由小寫字母 a-z 組成。 提示: 你需要優化回溯算法以通過更大數據量的測試。你能否早點停止回溯？ 如果當前單詞不存在于所有單詞的前綴中，則可以立即停止回溯。什么樣的數據結構可以有效地執行這樣的操作？散列表是否可行？為什么？ 前綴樹如何？如果你想學習如何實現一個基本的前綴樹，請先查看這個問題： 實現Trie（前綴樹）。 ``` ``` ## 前置知識 - 前綴樹 - DFS ## 公司 - 百度 - 字節 ## 思路 我們需要對矩陣中每一項都進行深度優先遍歷（DFS）。 遞歸的終點是 1. 超出邊界 2. 遞歸路徑上組成的單詞不在 words 的前綴。 比如題目示例：words = \["oath","pea","eat","rain"\]，那么對于 oa，oat 滿足條件，因為他們都是 oath 的前綴，但是 oaa 就不滿足條件。 為了防止環的出現，我們需要記錄訪問過的節點。而返回結果是需要去重的。出于簡單考慮，我們使用集合（set），最后返回的時候重新轉化為 list。 剛才我提到了一個關鍵詞“前綴”，我們考慮使用前綴樹來優化。使得復雜度降低為O(h)O(h)O(h), 其中 h 是前綴樹深度，也就是最長的字符串長度。  ## 關鍵點 - 前綴樹（也叫字典樹），英文名 Trie（讀作 tree 或者 try） - DFS - hashmap 結合 dfs 記錄訪問過的元素的時候，注意結束之后需要將 hashmap 的值重置。（下方代碼的`del seen[(i, j)]`） ## 代碼 - 語言支持：Python3 Python3 Code： 關于 Trie 的代碼: ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Trie</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">__init__</span><span class="hljs-params">(self)</span>:</span> <span class="hljs-string">""" Initialize your data structure here. """</span> self.Trie = {} <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">insert</span><span class="hljs-params">(self, word)</span>:</span> <span class="hljs-string">""" Inserts a word into the trie. :type word: str :rtype: void """</span> curr = self.Trie <span class="hljs-keyword">for</span> w <span class="hljs-keyword">in</span> word: <span class="hljs-keyword">if</span> w <span class="hljs-keyword">not</span> <span class="hljs-keyword">in</span> curr: curr[w] = {} curr = curr[w] curr[<span class="hljs-string">'#'</span>] = <span class="hljs-params">1</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">startsWith</span><span class="hljs-params">(self, prefix)</span>:</span> <span class="hljs-string">""" Returns if there is any word in the trie that starts with the given prefix. :type prefix: str :rtype: bool """</span> curr = self.Trie <span class="hljs-keyword">for</span> w <span class="hljs-keyword">in</span> prefix: <span class="hljs-keyword">if</span> w <span class="hljs-keyword">not</span> <span class="hljs-keyword">in</span> curr: <span class="hljs-keyword">return</span> <span class="hljs-keyword">False</span> curr = curr[w] <span class="hljs-keyword">return</span> <span class="hljs-keyword">True</span> ``` ``` 主邏輯代碼： ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">findWords</span><span class="hljs-params">(self, board: List[List[str]], words: List[str])</span> -> List[str]:</span> m = len(board) <span class="hljs-keyword">if</span> m == <span class="hljs-params">0</span>: <span class="hljs-keyword">return</span> [] n = len(board[<span class="hljs-params">0</span>]) trie = Trie() seen = <span class="hljs-keyword">None</span> res = set() <span class="hljs-keyword">for</span> word <span class="hljs-keyword">in</span> words: trie.insert(word) <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">dfs</span><span class="hljs-params">(s, i, j)</span>:</span> <span class="hljs-keyword">if</span> (i, j) <span class="hljs-keyword">in</span> seen <span class="hljs-keyword">or</span> i < <span class="hljs-params">0</span> <span class="hljs-keyword">or</span> i >= m <span class="hljs-keyword">or</span> j < <span class="hljs-params">0</span> <span class="hljs-keyword">or</span> j >= n <span class="hljs-keyword">or</span> <span class="hljs-keyword">not</span> trie.startsWith(s): <span class="hljs-keyword">return</span> s += board[i][j] seen[(i, j)] = <span class="hljs-keyword">True</span> <span class="hljs-keyword">if</span> s <span class="hljs-keyword">in</span> words: res.add(s) dfs(s, i + <span class="hljs-params">1</span>, j) dfs(s, i - <span class="hljs-params">1</span>, j) dfs(s, i, j + <span class="hljs-params">1</span>) dfs(s, i, j - <span class="hljs-params">1</span>) <span class="hljs-keyword">del</span> seen[(i, j)] <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(m): <span class="hljs-keyword">for</span> j <span class="hljs-keyword">in</span> range(n): seen = dict() dfs(<span class="hljs-string">""</span>, i, j) <span class="hljs-keyword">return</span> list(res) ``` ``` ## 相關題目 - [0208.implement-trie-prefix-tree](208.implement-trie-prefix-tree.html) - [0211.add-and-search-word-data-structure-design](211.add-and-search-word-data-structure-design.html) - [0472.concatenated-words](472.concatenated-words.html) - [0820.short-encoding-of-words](https://github.com/azl397985856/leetcode/blob/master/problems/820.short-encoding-of-words.md) - [1032.stream-of-characters](https://github.com/azl397985856/leetcode/blob/master/problems/1032.stream-of-characters.md)