0079. 單詞搜索 · ttttt

# 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">``` public class LC79WordSearch { public boolean exist(char[][] board, String word) { if (board == null || word == null) return false; if (word.length() == 0) return true; if (board.length == 0) return false; int rows = board.length; int cols = board[0].length; for (int r = 0; r < rows; r++) { for (int c = 0; c < cols; c++) { // scan board, start with word first character if (board[r][c] == word.charAt(0)) { if (helper(board, word, r, c, 0)) { return true; } } } } return false; } private boolean helper(char[][] board, String word, int r, int c, int start) { // already match word all characters, return true if (start == word.length()) return true; if (!isValid(board, r, c) || board[r][c] != word.charAt(start)) return false; // mark visited board[r][c] = '*'; boolean res = helper(board, word, r - 1, c, start + 1) // 上 || helper(board, word, r + 1, c, start + 1) // 下 || helper(board, word, r, c - 1, start + 1) // 左 || helper(board, word, r, c + 1, start + 1); // 右 // backtracking to start position board[r][c] = word.charAt(start); return res; } private boolean isValid(char[][] board, int r, int c) { return r >= 0 && r < board.length && c >= 0 && c < board[0].length; } } ``` ``` *Python3 Code* ``` <pre class="calibre18">``` class Solution: def exist(self, board: List[List[str]], word: str) -> bool: m = len(board) n = len(board[0]) def dfs(board, r, c, word, index): if index == len(word): return True if r < 0 or r >= m or c < 0 or c >= n or board[r][c] != word[index]: return False board[r][c] = '*' res = dfs(board, r - 1, c, word, index + 1) or dfs(board, r + 1, c, word, index + 1) or dfs(board, r, c - 1, word, index + 1) or dfs(board, r, c + 1, word, index + 1) board[r][c] = word[index] return res for r in range(m): for c in range(n): if board[r][c] == word[0]: if dfs(board, r, c, word, 0): return True ``` ``` *Javascript Code* from [**@lucifer**](https://github.com/azl397985856) ``` <pre class="calibre18">``` /* * @lc app=leetcode id=79 lang=javascript * * [79] Word Search */ function DFS(board, row, col, rows, cols, word, cur) { // 邊界檢查 if (row >= rows || row < 0) return false; if (col >= cols || col < 0) return false; const item = board[row][col]; if (item !== word[cur]) return false; if (cur + 1 === word.length) return true; // 如果你用hashmap記錄訪問的字母，那么你需要每次backtrack的時候手動清除hashmap，并且需要額外的空間 // 這里我們使用一個little trick board[row][col] = null; // 上下左右 const res = DFS(board, row + 1, col, rows, cols, word, cur + 1) || DFS(board, row - 1, col, rows, cols, word, cur + 1) || DFS(board, row, col - 1, rows, cols, word, cur + 1) || DFS(board, row, col + 1, rows, cols, word, cur + 1); board[row][col] = item; return res; } /** * @param {character[][]} board * @param {string} word * @return {boolean} */ var exist = function (board, word) { if (word.length === 0) return true; if (board.length === 0) return false; const rows = board.length; const cols = board[0].length; for (let i = 0; i < rows; i++) { for (let j = 0; j < cols; j++) { const hit = DFS(board, i, j, rows, cols, word, 0); if (hit) return true; } } return false; }; ``` ``` ## 參考（References） 1. [回溯法 Wiki](https://www.wikiwand.com/zh/%E5%9B%9E%E6%BA%AF%E6%B3%95)