107 lines
3.8 KiB
Markdown
107 lines
3.8 KiB
Markdown
|
- Leetcode - Word Search
|
||
|
|
collapsed:: true
|
||
|
|
- Times:
|
||
|
|
- Time when completed: 10:47
|
||
|
|
- Time taken to complete: 30mins
|
||
|
|
- DONE Revisions:
|
||
|
|
SCHEDULED: <2023-05-30 Tue>
|
||
|
|
:LOGBOOK:
|
||
|
|
* State "DONE" from "LATER" [2023-05-11 Thu 20:29]
|
||
|
|
* State "DONE" from "LATER" [2023-05-23 Tue 20:26]
|
||
|
|
:END:
|
||
|
|
- [[May 11th, 2023]] 11:43
|
||
|
|
- Tags:
|
||
|
|
- Algorithms: #DFS #DFS_preorder #backtrack
|
||
|
|
- Data structures: #vector_2d
|
||
|
|
- Difficulty: #difficulty_medium
|
||
|
|
- Platforms: #leetcode
|
||
|
|
- Links:
|
||
|
|
- [Link to the problem](https://leetcode.com/problems/word-search/description/)
|
||
|
|
- Problem:
|
||
|
|
- 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.
|
||
|
|
- **Follow up:** Could you use search pruning to make your solution faster with a larger `board`?
|
||
|
|
- Examples:
|
||
|
|
- https://assets.leetcode.com/uploads/2020/11/04/word2.jpg
|
||
|
|
- https://assets.leetcode.com/uploads/2020/11/04/word-1.jpg
|
||
|
|
- https://assets.leetcode.com/uploads/2020/10/15/word3.jpg
|
||
|
|
- ```
|
||
|
|
Example 1:
|
||
|
|
|
||
|
|
Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
|
||
|
|
Output: true
|
||
|
|
|
||
|
|
Example 2:
|
||
|
|
|
||
|
|
Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
|
||
|
|
Output: true
|
||
|
|
|
||
|
|
Example 3:
|
||
|
|
|
||
|
|
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.
|
||
|
|
- Thoughts:
|
||
|
|
- Intuition:
|
||
|
|
- The solution is simple, first loop over the board to find a starting point, then start dfs there.
|
||
|
|
- The only caveat is remember to add a simple backtracking to prevent the case when a route is invalid, but still used the visited[][] array.
|
||
|
|
- Approach:
|
||
|
|
- Loop over the board
|
||
|
|
- DFS from that point
|
||
|
|
- Solution:
|
||
|
|
- Code
|
||
|
|
- ``` java
|
||
|
|
class Solution {
|
||
|
|
boolean[][] visited;
|
||
|
|
boolean dfs(char[][] board, String word, int x, int y, int start) {
|
||
|
|
if (start == word.length()) {
|
||
|
|
return true;
|
||
|
|
}
|
||
|
|
if (x < 0 || x >= board.length || y < 0 || y >= board[0].length) {
|
||
|
|
return false;
|
||
|
|
}
|
||
|
|
if (visited[x][y]) {
|
||
|
|
return false;
|
||
|
|
}
|
||
|
|
if (board[x][y] == word.charAt(start)) {
|
||
|
|
visited[x][y] = true;
|
||
|
|
boolean found = dfs(board, word, x + 1, y, start + 1) ||
|
||
|
|
dfs(board, word, x - 1, y, start + 1) ||
|
||
|
|
dfs(board, word, x, y + 1, start + 1) ||
|
||
|
|
dfs(board, word, x, y - 1, start + 1);
|
||
|
|
if (!found) { // the backtracking
|
||
|
|
visited[x][y] = false;
|
||
|
|
return false;
|
||
|
|
} else {
|
||
|
|
return true;
|
||
|
|
}
|
||
|
|
} else {
|
||
|
|
return false;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
public boolean exist(char[][] board, String word) {
|
||
|
|
visited = new boolean[board.length][board[0].length];
|
||
|
|
// first, loop over the problems, then use dfs.
|
||
|
|
for (int i = 0; i < board.length; i++) {
|
||
|
|
for (int j = 0; j < board[0].length; j++) {
|
||
|
|
if (word.charAt(0) == board[i][j]) {
|
||
|
|
visited = new boolean[board.length][board[0].length];
|
||
|
|
if (dfs(board, word, i, j, 0)) {
|
||
|
|
return true;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
}
|
||
|
|
}
|
||
|
|
return false;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
```
|