Off-by-one on range boundaries
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Move from brute-force thinking to an efficient approach using array strategy.
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.lengthn = board[i].length1 <= m, n <= 61 <= word.length <= 15board and word consists of only lowercase and uppercase English letters.Follow up: Could you use search pruning to make your solution faster with a larger board?
Problem summary: 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.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Array · Backtracking
[["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]] "ABCCED"
[["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]] "SEE"
[["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]] "ABCB"
word-search-ii)class Solution {
public boolean exist(char[][] board, String word) {
int m = board.length, n = board[0].length;
for (int r = 0; r < m; r++) {
for (int c = 0; c < n; c++) {
if (dfs(board, word, r, c, 0)) return true;
}
}
return false;
}
private boolean dfs(char[][] board, String word, int r, int c, int i) {
if (i == word.length()) return true;
if (r < 0 || c < 0 || r >= board.length || c >= board[0].length) return false;
if (board[r][c] != word.charAt(i)) return false;
char temp = board[r][c];
board[r][c] = '#';
boolean found = dfs(board, word, r + 1, c, i + 1)
|| dfs(board, word, r - 1, c, i + 1)
|| dfs(board, word, r, c + 1, i + 1)
|| dfs(board, word, r, c - 1, i + 1);
board[r][c] = temp;
return found;
}
}
func exist(board [][]byte, word string) bool {
m, n := len(board), len(board[0])
var dfs func(r, c, i int) bool
dfs = func(r, c, i int) bool {
if i == len(word) {
return true
}
if r < 0 || c < 0 || r >= m || c >= n || board[r][c] != word[i] {
return false
}
temp := board[r][c]
board[r][c] = '#'
found := dfs(r+1, c, i+1) || dfs(r-1, c, i+1) || dfs(r, c+1, i+1) || dfs(r, c-1, i+1)
board[r][c] = temp
return found
}
for r := 0; r < m; r++ {
for c := 0; c < n; c++ {
if dfs(r, c, 0) {
return true
}
}
}
return false
}
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
m, n = len(board), len(board[0])
def dfs(r: int, c: int, i: int) -> bool:
if i == len(word):
return True
if r < 0 or c < 0 or r >= m or c >= n or board[r][c] != word[i]:
return False
temp = board[r][c]
board[r][c] = '#'
found = (
dfs(r + 1, c, i + 1) or
dfs(r - 1, c, i + 1) or
dfs(r, c + 1, i + 1) or
dfs(r, c - 1, i + 1)
)
board[r][c] = temp
return found
for r in range(m):
for c in range(n):
if dfs(r, c, 0):
return True
return False
impl Solution {
pub fn exist(board: Vec<Vec<char>>, word: String) -> bool {
let mut board = board;
let m = board.len() as i32;
let n = board[0].len() as i32;
let w: Vec<char> = word.chars().collect();
fn dfs(board: &mut Vec<Vec<char>>, w: &Vec<char>, r: i32, c: i32, i: usize, m: i32, n: i32) -> bool {
if i == w.len() {
return true;
}
if r < 0 || c < 0 || r >= m || c >= n {
return false;
}
let rr = r as usize;
let cc = c as usize;
if board[rr][cc] != w[i] {
return false;
}
let temp = board[rr][cc];
board[rr][cc] = '#';
let found = dfs(board, w, r + 1, c, i + 1, m, n)
|| dfs(board, w, r - 1, c, i + 1, m, n)
|| dfs(board, w, r, c + 1, i + 1, m, n)
|| dfs(board, w, r, c - 1, i + 1, m, n);
board[rr][cc] = temp;
found
}
for r in 0..m {
for c in 0..n {
if dfs(&mut board, &w, r, c, 0, m, n) {
return true;
}
}
}
false
}
}
function exist(board: string[][], word: string): boolean {
const m = board.length;
const n = board[0].length;
const dfs = (r: number, c: number, i: number): boolean => {
if (i === word.length) return true;
if (r < 0 || c < 0 || r >= m || c >= n) return false;
if (board[r][c] !== word[i]) return false;
const temp = board[r][c];
board[r][c] = '#';
const found =
dfs(r + 1, c, i + 1) ||
dfs(r - 1, c, i + 1) ||
dfs(r, c + 1, i + 1) ||
dfs(r, c - 1, i + 1);
board[r][c] = temp;
return found;
};
for (let r = 0; r < m; r++) {
for (let c = 0; c < n; c++) {
if (dfs(r, c, 0)) return true;
}
}
return false;
}
Use this to step through a reusable interview workflow for this problem.
Generate every possible combination without any filtering. At each of n positions we choose from up to n options, giving nⁿ total candidates. Each candidate takes O(n) to validate. No pruning means we waste time on clearly invalid partial solutions.
Backtracking explores a decision tree, but prunes branches that violate constraints early. Worst case is still factorial or exponential, but pruning dramatically reduces the constant factor in practice. Space is the recursion depth (usually O(n) for n-level decisions).
Review these before coding to avoid predictable interview regressions.
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Wrong move: Mutable state leaks between branches.
Usually fails on: Later branches inherit selections from earlier branches.
Fix: Always revert state changes immediately after recursive call.