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)