Word Search
You're given an m x n grid of letters board and a string word. Return true if word can be spelled by a path through the grid that starts at any cell and moves one step at a time up, down, left or right (not diagonally), where each cell's letter matches the next letter of word. A cell may be used at most once within a single path. Otherwise return false.
Examples
board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED" returns true
Start at the A in the top-left corner, go right to B and C, down to the C below it, down again to E, then left to D. Each step moves to a neighboring cell and no cell is used twice.
board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB" returns false
A, B, C along the top row match the first three letters, but the board's only B has already been used, and a cell can't be used twice.
Constraints
- 1 <= m, n <= 6
- 1 <= word.length <= 15
Hints
You're matching one character at a time and you can't revisit cells, how do you undo a step when a branch fails?
DFS from each cell, marking the current cell visited and unmarking on the way back.
Iterate over each cell. From a matching first letter, DFS with index i: if i == word.length, return true. Temporarily mark the cell (e.g., overwrite with a sentinel). Recurse into the four neighbors with index i + 1. Restore the cell and return whether any branch succeeded.
Drill This: Your Approach First
Approach
Try every cell as a start and extend the match one letter at a time with dfs(i, j, k), which asks whether word[k:] can be spelled starting at cell (i, j). It fails on an out-of-bounds cell or a letter mismatch and succeeds once k reaches L = len(word). Before exploring the four neighbors, overwrite the cell with '#' so the path can't reuse it, then restore the letter when backing out. The cell you came from is marked, so each step has at most 3 real options.
Time
O(m * n * 3^L)
Space
O(L)
Pitfall
Solutions
class Solution {
public boolean exist(char[][] board, String word) {
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
if (dfs(board, word, i, j, 0)) return true;
}
}
return false;
}
private boolean dfs(char[][] board, String word, int i, int j, int k) {
if (k == word.length()) return true;
if (i < 0 || j < 0 || i >= board.length || j >= board[0].length
|| board[i][j] != word.charAt(k)) return false;
char tmp = board[i][j];
board[i][j] = '#';
boolean found = dfs(board, word, i + 1, j, k + 1)
|| dfs(board, word, i - 1, j, k + 1)
|| dfs(board, word, i, j + 1, k + 1)
|| dfs(board, word, i, j - 1, k + 1);
board[i][j] = tmp;
return found;
}
}class Solution:
def exist(self, board, word: str) -> bool:
rows, cols = len(board), len(board[0])
def dfs(i, j, k):
if k == len(word):
return True
if i < 0 or j < 0 or i >= rows or j >= cols or board[i][j] != word[k]:
return False
tmp = board[i][j]
board[i][j] = '#'
found = (dfs(i + 1, j, k + 1) or dfs(i - 1, j, k + 1)
or dfs(i, j + 1, k + 1) or dfs(i, j - 1, k + 1))
board[i][j] = tmp
return found
for i in range(rows):
for j in range(cols):
if dfs(i, j, 0):
return True
return False