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.
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.
Solution
public class Solution {
public bool Exist(char[][] board, string word) {
int rows = board.Length;
int cols = board[0].Length;
// Check if there are enough characters in the grid
if (rows * cols < word.Length) {
return false;
}
for (int row = 0; row < rows; row++) {
for (int col = 0; col < cols; col++) {
if (Backtrack(board, word, row, col, 0)) {
return true;
}
}
}
return false;
}
private bool Backtrack(char[][] board, string word, int row, int col, int index) {
// Check if we've found the word
if (index >= word.Length) {
return true;
}
int rows = board.Length;
int cols = board[0].Length;
// Check if we're out of bounds or the character doesn't match
if (row < 0 || row == rows || col < 0 || col == cols || board[row][col] != word[index]) {
return false;
}
// Mark the current cell as visited
char temp = board[row][col];
board[row][col] = '#';
// Check all four directions
int[] rowOffsets = {0, 1, 0, -1};
int[] colOffsets = {1, 0, -1, 0};
for (int d = 0; d < 4; d++) {
if (Backtrack(board, word, row + rowOffsets[d], col + colOffsets[d], index + 1)) {
return true;
}
}
// Unmark the current cell and return false
board[row][col] = temp;
return false;
}
}
The time complexity of the algorithm is O(N), where N is the total number of cells in the grid. This is because each cell in the grid is visited at most once.
The space complexity of the algorithm is O(N) in the worst case. This could occur in a situation where the depth of the recursive call stack goes N deep. For example, consider a worst-case scenario where the grid is filled with the same character and the word to be found is made up of that character repeated. The algorithm would explore all possible paths, which could potentially fill the call stack with N recursive calls.
