1. Problem Statement (Simple Explanation)
You’re given:
A 2D grid of characters board (size m x n).
A string word.
You must determine if word exists in the grid.
Rules:
The word must be constructed from letters of sequentially adjacent cells.
Adjacent cells are horizontally or vertically neighboring (no diagonals).
The same cell cannot be used more than once in a given word path.
Return true if word exists in board, otherwise false.
2. Examples
Example 1:
Input:
board = [
["A","B","C","E"],
["S","F","C","S"],
["A","D","E","E"]
]
word = "ABCCED"
One possible path:
(0,0)A → (0,1)B → (0,2)C → (1,2)C → (2,2)E → (2,1)D
Output: true
Example 2:
Input:
board = [
["A","B","C","E"],
["S","F","C","S"],
["A","D","E","E"]
]
word = "SEE"
Path:
(1,3)S → (2,3)E → (2,2)E
Output: true
Example 3:
Input:
board = [
["A","B","C","E"],
["S","F","C","S"],
["A","D","E","E"]
]
word = "ABCB"
You would need to reuse the 'B' at (0,1) to form the word, which is not allowed.
Output: false
3. Approach – Backtracking (DFS) with In-Place Visited Marking
We need to see if there's a path in the grid that spells the word.
Key Ideas:
For each cell (i, j) in the board:
If board[i][j] == word[0], start DFS from that cell.
DFS function dfs(r, c, idx):
r, c = current cell.
idx = index in word that we’re trying to match at (r, c).
Base conditions:
If idx == len(word) → we’ve matched all characters → return true.
If r or c is out of bounds → return false.
If board[r][c] != word[idx] → return false.
If this cell is already visited in the current path → return false.
Mark the cell as visited:
Common trick: temporarily change board[r][c] to some sentinel (e.g., '#') to mark it as visited, then restore after recursion.
Recurse in four directions:
Up: (r - 1, c)
Down: (r + 1, c)
Left: (r, c - 1)
Right: (r, c + 1)
If any recursive call returns true, propagate true.
After exploring all directions, restore the original character (backtrack) and return false if no path found.
Pseudo-code:
Let:
m = number of rows, n = number of cols, L = len(word).
In worst case:
We start at each cell → O(m·n).
DFS depth can go up to L, and at each step, up to 4 directions.
Upper bound: O(m·n·4L) in the worst theoretical case.
But with constraints (m,n ≤ 6, L ≤ 15) and pruning (mismatch & visited), it's fine.
Space:
Recursion depth O(L), plus in-place marking, so O(L) extra.
Pruning Ideas (Follow-up):
To optimize for larger boards:
Count frequency of characters in word and board:
If any character in word appears more times than in the board, early return false.
Sometimes beneficial to:
If word[0] is rarer than word[-1], search using word in reverse direction.
Our constraints are small, so not required here, but good to mention.
4. Java code
6. C++ code
7. Python code
8. JavaScript code
Comments
Post a Comment