79.Word Search === ###### tags: `Medium`,`Array`,`Backtracking`,`Matrix` [79. Word Search](https://leetcode.com/problems/word-search/) ### 題目描述 Given an `m x n` grid of characters `board` and a string `word`, return `true` if `word` exists in the grid. The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once. ### 範例 ![](https://assets.leetcode.com/uploads/2020/11/04/word2.jpg) ``` Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]] word = "ABCCED" Output: true ``` ![](https://assets.leetcode.com/uploads/2020/11/04/word-1.jpg) ``` Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]] word = "SEE" Output: true ``` ![](https://assets.leetcode.com/uploads/2020/10/15/word3.jpg) ``` Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]] word = "ABCB" Output: false ``` **Constraints**: * `m == board.length` * `n = board[i].length` * `1 <= m, n <= 6` * `1 <= word.length <= 15` * `board` and `word` consists of only lowercase and uppercase English letters. ### 解答 #### Python 小羊解完不貼我先貼 ```python= class Solution(object): def exist(self, board, word): """ :type board: List[List[str]] :type word: str :rtype: bool """ row_len = len(board[0]) col_len = len(board) word_len = len(word) # can add conditions before searching # trivial: word length must be less than board size # big improve: count and compare each character # Za def worudoSearch(row, col, word_idx): if word_idx >= word_len: return True elif 0 <= row < col_len and 0 <= col < row_len and board[row][col] == word[word_idx]: # store and RECOVER visited, credit to Marsgoat tmp = board[row][col] board[row][col] = '' if worudoSearch(row+1, col, word_idx+1) or worudoSearch(row, col+1, word_idx+1) \ or worudoSearch(row-1, col, word_idx+1) or worudoSearch(row, col-1, word_idx+1): return True board[row][col] = tmp # loop through for row in range(col_len): for col in range(row_len): if worudoSearch(row, col, 0): return True return False ``` > [name=DT] [time= Nov 24, 2022] 感覺很好玩,我也來貼一下 ```python= class Solution: def exist(self, board: List[List[str]], word: str) -> bool: m, n = len(board), len(board[0]) if len(word) > m * n: return False if not (cnt:=Counter(word)) <= Counter(chain(*board)): return False if cnt[word[0]] > cnt[word[-1]]: word = word[::-1] def dfs(i, j, s = 0): if s == len(word): return True if 0 <= i < m and 0 <= j < n and board[i][j] == word[s]: board[i][j] = '#' children = [(i+1, j), (i-1, j), (i, j+1), (i, j-1)] result = any(dfs(ci, cj, s+1) for ci, cj in children) board[i][j] = word[s] return result return False return any(dfs(i, j) for i, j in product(range(m), range(n))) ``` > 解完後發現很久之前submit過了,之前寫的版本中沒有4~9行的檢查也可以通過,只是會比較慢一點。 > [name=Yen-Chi Chen][time=Thu, Nov 24, 2022 10:19 PM] 凡人Backtracking ```python= class Solution: def exist(self, board: List[List[str]], word: str) -> bool: m, n = len(board), len(board[0]) def dfs(x, y, step): if x < 0 or x == n or y < 0 or y == m or word[step] != board[y][x]: return False if step == len(word) - 1: return True # Backtracking ori = board[y][x] board[y][x] = '#' found = dfs(x-1, y, step+1) or dfs(x+1, y, step+1) or dfs(x, y-1, step+1) or dfs(x, y+1, step+1) board[y][x] = ori return found for y in range(m): for x in range(n): if dfs(x, y, 0): return True return False ``` > [name=Kobe Bryant] [time=Nov 25, 2022] #### C++ ```cpp= vector<vector<int>> dirs{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; bool search(vector<vector<char>>& board, int row, int col, string& word, int index) { if(row < 0 || col < 0 || row == board.size() || col == board[0].size()) return false; if(board[row][col] != word[index]) return false; if(index == word.size()-1) return true; char orig_c = board[row][col]; board[row][col] = '#'; bool res = false; for(auto& d : dirs) res |= search(board, row+d[0], col+d[1], word, index+1); board[row][col] = orig_c; return res; } bool exist(vector<vector<char>>& board, string word) { if(board.size() == 0 || board[0].size() == 0) return false; int row_n = board.size(), col_n = board[0].size(); for(int row = 0; row < row_n; row++) { for(int col = 0; col < col_n; col++) if(search(board, row, col, word, 0)) return true; } return false; } ``` Time: $O(M*N*4^L)$ 最多走M*N格, 每格最走4個方向, 走字串長度(L)步 Extra Space: $O(1)$ > [name=XD] [time= Nov 24, 2022] #### Javascript ```javascript= function exist(board, word) { for (let i = 0; i < board.length; i++) { for (let j = 0; j < board[0].length; j++) { if (board[i][j] === word[0]) { const start = [i, j, 1]; if (search(board, word, start)) return true; } } } return false; } function search(board, word, start) { const isInBounds = (x, y, xLength, yLength) => x < xLength && x >= 0 && y < yLength && y >= 0; const [x, y, step] = start; board[x][y] = ''; // 跟大家學習,不用visited了 if (step === word.length) return true; const neighbors = [ [x + 1, y], [x - 1, y], [x, y + 1], [x, y - 1], ]; for (const [nx, ny] of neighbors) { if (!isInBounds(nx, ny, board.length, board[0].length)) continue; if (board[nx][ny] === word[step]) { if (search(board, word, [nx, ny, step + 1])) return true; } } board[x][y] = word[step - 1]; return false; } ``` > 唐神通靈大師太神啦,只看錯誤case就知道是visited沒有重置,有夠強,學習了。 > [name=Marsgoat] [time= Dec 1, 2022] ### Reference [回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)