<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>

                ??一站式輕松地調用各大LLM模型接口,支持GPT4、智譜、豆包、星火、月之暗面及文生圖、文生視頻 廣告
                # 0079. 單詞搜索 ## 題目地址(79. 單詞搜索) <https://leetcode-cn.com/problems/word-search/> ## 題目描述 ``` <pre class="calibre18">``` 給定一個二維網格和一個單詞,找出該單詞是否存在于網格中。 單詞必須按照字母順序,通過相鄰的單元格內的字母構成,其中“相鄰”單元格是那些水平相鄰或垂直相鄰的單元格。同一個單元格內的字母不允許被重復使用。 示例: board = [ ['A','B','C','E'], ['S','F','C','S'], ['A','D','E','E'] ] 給定 word = "ABCCED", 返回 true 給定 word = "SEE", 返回 true 給定 word = "ABCB", 返回 false 提示: board 和 word 中只包含大寫和小寫英文字母。 1 <= board.length <= 200 1 <= board[i].length <= 200 1 <= word.length <= 10^3 ``` ``` ## 前置知識 - 回溯 ## 公司 - 阿里 - 騰訊 - 百度 - 字節 ## 思路 在 2D 表中搜索是否有滿足給定單詞的字符組合,要求所有字符都是相鄰的(方向不限). 題中也沒有要求字符的起始和結束位置。 在起始位置不確定的情況下,掃描二維數組,找到字符跟給定單詞的第一個字符相同的,四個方向(上,下,左,右)分別 DFS 搜索, 如果任意方向滿足條件,則返回結果。不滿足,回溯,重新搜索。 舉例說明:如圖二維數組,單詞:"SEE" ``` <pre class="calibre18">``` 1. 掃描二維數組,找到board[1,0] = word[0],匹配單詞首字母。 2. 做DFS(上,下,左,右 四個方向) 如下圖: ``` ``` ![](https://img.kancloud.cn/d1/18/d11892c7c2101152c4ee7769d1940231_1368x451.jpg) 起始位置(1,0),判斷相鄰的字符是否匹配單詞下一個字符 `E`. ``` <pre class="calibre18">``` 1. 標記當前字符(1,0)為已經訪問過,board[1][0] = '*' 2. 上(0,0)字符為 'A' 不匹配, 3. 下(2,0)字符為 'A',不匹配, 4. 左(-1,0)超越邊界,不匹配, 5. 右(1,1)字符 'F',不匹配 如下圖: ``` ``` ![](https://img.kancloud.cn/5c/b2/5cb22965eb2709568a8c3fed5f830946_1172x566.jpg) 由于從起始位置 DFS 都不滿足條件,所以 ``` <pre class="calibre18">``` 1. 回溯,標記起始位置(1,0)為未訪問。board[1][0] = 'S'. 2. 然后繼續掃描二維數組,找到下一個起始位置(1,3) 如下圖: ``` ``` ![](https://img.kancloud.cn/21/ba/21ba0d8957ff9153faa57907124077ce_1210x467.jpg) 起始位置(1,3),判斷相鄰的字符是否匹配單詞下一個字符 `E`. ``` <pre class="calibre18">``` 1. 標記當前字符(1, 3)為已經訪問過,board[1][3] = '*' 2. 上(0,3)字符為 'E', 匹配, 繼續DFS搜索(參考位置為(0,3)位置DFS搜索步驟描述) 3. 下(2,3)字符為 'E',匹配, #2匹配,先進行#2 DFS搜索,由于#2 DFS搜索沒有找到與單詞匹配,繼續DFS搜索(參考位置為(2,3)DFS搜索步驟描述) 4. 左(1,2)字符為 'C',不匹配, 5. 右(1,4)超越邊界,不匹配 如下圖: ``` ``` ![](https://img.kancloud.cn/28/b9/28b95d9d8a6d64e2d5eddf4ac692712a_1242x515.jpg) 位置(0,3)滿足條件,繼續 DFS,判斷相鄰的字符是否匹配單詞下一個字符 `E` ``` <pre class="calibre18">``` 1. 標記當前字符(0,3)為已經訪問過,board[0][3] = '*' 2. 上 (-1,3)超越邊界,不匹配 3. 下(1,3)已經訪問過, 4. 左(0,2)字符為 'C',不匹配 5. 右(1,4)超越邊界,不匹配 如下圖 ``` ``` ![](https://img.kancloud.cn/77/a6/77a6e17d9c561f78211e793fca940a7e_1071x417.jpg) 從位置(0,3)DFS 不滿足條件,繼續位置(2,3)DFS 搜索 ``` <pre class="calibre18">``` 1. 回溯,標記起始位置(0,3)為未訪問。board[0][3] = 'E'. 2. 回到滿足條件的位置(2,3),繼續DFS搜索,判斷相鄰的字符是否匹配單詞下一個字符 'E' 3. 上 (1,3)已訪問過 4. 下(3,3)超越邊界,不匹配 5. 左(2,2)字符為 'E',匹配 6. 右(2,4)超越邊界,不匹配 如下圖: ``` ``` ![](https://img.kancloud.cn/b5/a5/b5a5e734042da362674f76df83ebcdb8_1121x449.jpg) 單詞匹配完成,滿足條件,返回 `True`. ![](https://img.kancloud.cn/b3/0b/b30b1e67572b6b31f78ded7f7cb43f6d_1233x420.jpg) #### 復雜度分析 - *時間復雜度:*`O(m*n) - m 是二維數組行數, n 是二維數組列數` - *空間復雜度:*`O(1) - 這里在原數組中標記當前訪問過,沒有用到額外空間` > **注意**:如果用 Set 或者是 boolean\[\]\[\]來標記字符位置是否已經訪問過,需要額外的空間 `O(m*n)`. ## 關鍵點分析 - 遍歷二維數組的每一個點,找到起始點相同的字符,做 DFS - DFS 過程中,要記錄已經訪問過的節點,防止重復遍歷,這里(Java Code 中)用 `*` 表示當前已經訪問過,也可以用 Set 或者是 boolean\[\]\[\]數組記錄訪問過的節點位置。 - 是否匹配當前單詞中的字符,不符合回溯,這里記得把當前 `*` 重新設為當前字符。如果用 Set 或者是 boolean\[\]\[\]數組,記得把當前位置重設為沒有訪問過。 ## 代碼 (`Java/Javascript/Python3`) *Java Code* ``` <pre class="calibre18">``` <span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">LC79WordSearch</span> </span>{ <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">boolean</span> <span class="hljs-title">exist</span><span class="hljs-params">(<span class="hljs-keyword">char</span>[][] board, String word)</span> </span>{ <span class="hljs-keyword">if</span> (board == <span class="hljs-keyword">null</span> || word == <span class="hljs-keyword">null</span>) <span class="hljs-keyword">return</span> <span class="hljs-keyword">false</span>; <span class="hljs-keyword">if</span> (word.length() == <span class="hljs-params">0</span>) <span class="hljs-keyword">return</span> <span class="hljs-keyword">true</span>; <span class="hljs-keyword">if</span> (board.length == <span class="hljs-params">0</span>) <span class="hljs-keyword">return</span> <span class="hljs-keyword">false</span>; <span class="hljs-keyword">int</span> rows = board.length; <span class="hljs-keyword">int</span> cols = board[<span class="hljs-params">0</span>].length; <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> r = <span class="hljs-params">0</span>; r < rows; r++) { <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> c = <span class="hljs-params">0</span>; c < cols; c++) { <span class="hljs-title">// scan board, start with word first character</span> <span class="hljs-keyword">if</span> (board[r][c] == word.charAt(<span class="hljs-params">0</span>)) { <span class="hljs-keyword">if</span> (helper(board, word, r, c, <span class="hljs-params">0</span>)) { <span class="hljs-keyword">return</span> <span class="hljs-keyword">true</span>; } } } } <span class="hljs-keyword">return</span> <span class="hljs-keyword">false</span>; } <span class="hljs-function"><span class="hljs-keyword">private</span> <span class="hljs-keyword">boolean</span> <span class="hljs-title">helper</span><span class="hljs-params">(<span class="hljs-keyword">char</span>[][] board, String word, <span class="hljs-keyword">int</span> r, <span class="hljs-keyword">int</span> c, <span class="hljs-keyword">int</span> start)</span> </span>{ <span class="hljs-title">// already match word all characters, return true</span> <span class="hljs-keyword">if</span> (start == word.length()) <span class="hljs-keyword">return</span> <span class="hljs-keyword">true</span>; <span class="hljs-keyword">if</span> (!isValid(board, r, c) || board[r][c] != word.charAt(start)) <span class="hljs-keyword">return</span> <span class="hljs-keyword">false</span>; <span class="hljs-title">// mark visited</span> board[r][c] = <span class="hljs-string">'*'</span>; <span class="hljs-keyword">boolean</span> res = helper(board, word, r - <span class="hljs-params">1</span>, c, start + <span class="hljs-params">1</span>) <span class="hljs-title">// 上</span> || helper(board, word, r + <span class="hljs-params">1</span>, c, start + <span class="hljs-params">1</span>) <span class="hljs-title">// 下</span> || helper(board, word, r, c - <span class="hljs-params">1</span>, start + <span class="hljs-params">1</span>) <span class="hljs-title">// 左</span> || helper(board, word, r, c + <span class="hljs-params">1</span>, start + <span class="hljs-params">1</span>); <span class="hljs-title">// 右</span> <span class="hljs-title">// backtracking to start position</span> board[r][c] = word.charAt(start); <span class="hljs-keyword">return</span> res; } <span class="hljs-function"><span class="hljs-keyword">private</span> <span class="hljs-keyword">boolean</span> <span class="hljs-title">isValid</span><span class="hljs-params">(<span class="hljs-keyword">char</span>[][] board, <span class="hljs-keyword">int</span> r, <span class="hljs-keyword">int</span> c)</span> </span>{ <span class="hljs-keyword">return</span> r >= <span class="hljs-params">0</span> && r < board.length && c >= <span class="hljs-params">0</span> && c < board[<span class="hljs-params">0</span>].length; } } ``` ``` *Python3 Code* ``` <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">exist</span><span class="hljs-params">(self, board: List[List[str]], word: str)</span> -> bool:</span> m = len(board) n = len(board[<span class="hljs-params">0</span>]) <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">dfs</span><span class="hljs-params">(board, r, c, word, index)</span>:</span> <span class="hljs-keyword">if</span> index == len(word): <span class="hljs-keyword">return</span> <span class="hljs-keyword">True</span> <span class="hljs-keyword">if</span> r < <span class="hljs-params">0</span> <span class="hljs-keyword">or</span> r >= m <span class="hljs-keyword">or</span> c < <span class="hljs-params">0</span> <span class="hljs-keyword">or</span> c >= n <span class="hljs-keyword">or</span> board[r][c] != word[index]: <span class="hljs-keyword">return</span> <span class="hljs-keyword">False</span> board[r][c] = <span class="hljs-string">'*'</span> res = dfs(board, r - <span class="hljs-params">1</span>, c, word, index + <span class="hljs-params">1</span>) <span class="hljs-keyword">or</span> dfs(board, r + <span class="hljs-params">1</span>, c, word, index + <span class="hljs-params">1</span>) <span class="hljs-keyword">or</span> dfs(board, r, c - <span class="hljs-params">1</span>, word, index + <span class="hljs-params">1</span>) <span class="hljs-keyword">or</span> dfs(board, r, c + <span class="hljs-params">1</span>, word, index + <span class="hljs-params">1</span>) board[r][c] = word[index] <span class="hljs-keyword">return</span> res <span class="hljs-keyword">for</span> r <span class="hljs-keyword">in</span> range(m): <span class="hljs-keyword">for</span> c <span class="hljs-keyword">in</span> range(n): <span class="hljs-keyword">if</span> board[r][c] == word[<span class="hljs-params">0</span>]: <span class="hljs-keyword">if</span> dfs(board, r, c, word, <span class="hljs-params">0</span>): <span class="hljs-keyword">return</span> <span class="hljs-keyword">True</span> ``` ``` *Javascript Code* from [**@lucifer**](https://github.com/azl397985856) ``` <pre class="calibre18">``` <span class="hljs-title">/* * @lc app=leetcode id=79 lang=javascript * * [79] Word Search */</span> <span class="hljs-function"><span class="hljs-keyword">function</span> <span class="hljs-title">DFS</span>(<span class="hljs-params">board, row, col, rows, cols, word, cur</span>) </span>{ <span class="hljs-title">// 邊界檢查</span> <span class="hljs-keyword">if</span> (row >= rows || row < <span class="hljs-params">0</span>) <span class="hljs-keyword">return</span> <span class="hljs-params">false</span>; <span class="hljs-keyword">if</span> (col >= cols || col < <span class="hljs-params">0</span>) <span class="hljs-keyword">return</span> <span class="hljs-params">false</span>; <span class="hljs-keyword">const</span> item = board[row][col]; <span class="hljs-keyword">if</span> (item !== word[cur]) <span class="hljs-keyword">return</span> <span class="hljs-params">false</span>; <span class="hljs-keyword">if</span> (cur + <span class="hljs-params">1</span> === word.length) <span class="hljs-keyword">return</span> <span class="hljs-params">true</span>; <span class="hljs-title">// 如果你用hashmap記錄訪問的字母, 那么你需要每次backtrack的時候手動清除hashmap,并且需要額外的空間</span> <span class="hljs-title">// 這里我們使用一個little trick</span> board[row][col] = <span class="hljs-params">null</span>; <span class="hljs-title">// 上下左右</span> <span class="hljs-keyword">const</span> res = DFS(board, row + <span class="hljs-params">1</span>, col, rows, cols, word, cur + <span class="hljs-params">1</span>) || DFS(board, row - <span class="hljs-params">1</span>, col, rows, cols, word, cur + <span class="hljs-params">1</span>) || DFS(board, row, col - <span class="hljs-params">1</span>, rows, cols, word, cur + <span class="hljs-params">1</span>) || DFS(board, row, col + <span class="hljs-params">1</span>, rows, cols, word, cur + <span class="hljs-params">1</span>); board[row][col] = item; <span class="hljs-keyword">return</span> res; } <span class="hljs-title">/** * @param {character[][]} board * @param {string} word * @return {boolean} */</span> <span class="hljs-keyword">var</span> exist = <span class="hljs-function"><span class="hljs-keyword">function</span> (<span class="hljs-params">board, word</span>) </span>{ <span class="hljs-keyword">if</span> (word.length === <span class="hljs-params">0</span>) <span class="hljs-keyword">return</span> <span class="hljs-params">true</span>; <span class="hljs-keyword">if</span> (board.length === <span class="hljs-params">0</span>) <span class="hljs-keyword">return</span> <span class="hljs-params">false</span>; <span class="hljs-keyword">const</span> rows = board.length; <span class="hljs-keyword">const</span> cols = board[<span class="hljs-params">0</span>].length; <span class="hljs-keyword">for</span> (<span class="hljs-keyword">let</span> i = <span class="hljs-params">0</span>; i < rows; i++) { <span class="hljs-keyword">for</span> (<span class="hljs-keyword">let</span> j = <span class="hljs-params">0</span>; j < cols; j++) { <span class="hljs-keyword">const</span> hit = DFS(board, i, j, rows, cols, word, <span class="hljs-params">0</span>); <span class="hljs-keyword">if</span> (hit) <span class="hljs-keyword">return</span> <span class="hljs-params">true</span>; } } <span class="hljs-keyword">return</span> <span class="hljs-params">false</span>; }; ``` ``` ## 參考(References) 1. [回溯法 Wiki](https://www.wikiwand.com/zh/%E5%9B%9E%E6%BA%AF%E6%B3%95)
                  <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>

                              哎呀哎呀视频在线观看