<ruby id="bdb3f"></ruby>

    <p id="bdb3f"><cite id="bdb3f"></cite></p>

      <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
        <p id="bdb3f"><cite id="bdb3f"></cite></p>

          <pre id="bdb3f"></pre>
          <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

          <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
          <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

          <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                <ruby id="bdb3f"></ruby>

                ThinkChat2.0新版上線,更智能更精彩,支持會話、畫圖、視頻、閱讀、搜索等,送10W Token,即刻開啟你的AI之旅 廣告
                # 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 是前綴樹深度,也就是最長的字符串長度。 ![](https://img.kancloud.cn/34/0c/340c37fc6c68e2b73809d19d20a78a96_827x602.jpg) ## 關鍵點 - 前綴樹(也叫字典樹),英文名 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)
                  <ruby id="bdb3f"></ruby>

                  <p id="bdb3f"><cite id="bdb3f"></cite></p>

                    <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
                      <p id="bdb3f"><cite id="bdb3f"></cite></p>

                        <pre id="bdb3f"></pre>
                        <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

                        <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
                        <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

                        <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                              <ruby id="bdb3f"></ruby>

                              哎呀哎呀视频在线观看