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 cell, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.
Constraints:
- m == board.length
- n == board[i].length
- 1 <= m * n <= 2 * 10^5
- 1 <= word.length <= 3 * 10^4
- board and word consists only of lowercase and uppercase English letters
Examples:
Input: [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], "ABCCED"
Output: true
Explanation: The word can be found in the grid by starting at the top left cell and moving right, then down, then right again.
Input: [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], "SEE"
Output: true
Explanation: The word can be found in the grid by starting at the middle left cell and moving right, then down.
Input: [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], "ABCB"
Output: false
Explanation: The word cannot be found in the grid because the letter 'B' is not adjacent to the letter 'C'.
Solutions
Depth-First Search
The solution uses a depth-first search approach to traverse the grid and find the word. It starts by checking each cell in the grid to see if it matches the first letter of the word. If it does, it then checks the adjacent cells to see if they match the next letter in the word, and so on. If it finds a path that matches the entire word, it returns true. If it exhausts all possible paths without finding a match, it returns false.
public boolean exist(char[][] board, String word) {
int rows = board.length, cols = board[0].length;
public boolean dfs(int r, int c, int index) {
if (index == word.length()) return true;
if (r < 0 || c < 0 || r >= rows || c >= cols || word.charAt(index) != board[r][c]) return false;
char temp = board[r][c];
board[r][c] = '#';
boolean found = dfs(r + 1, c, index + 1) || dfs(r - 1, c, index + 1) || dfs(r, c + 1, index + 1) || dfs(r, c - 1, index + 1);
board[r][c] = temp;
return found;
}
for (int i = 0;
i < rows;
i++) {
for (int j = 0;
j < cols;
j++) {
if (dfs(i, j, 0)) return true;
}
}
return false;
}Follow-up:
How would you optimize the solution to handle very large grids and words?
