LeetCode 79: Word Search (Backtracking DFS on Grid)
LeetCode 79MatrixBacktrackingDFSToday we solve LeetCode 79 - Word Search.
Source: https://leetcode.com/problems/word-search/
English
Problem Summary
Given a 2D board of letters and a target string word, determine whether the word exists in the grid. You may move up/down/left/right, and each cell can be used at most once in one path.
Key Insight
This is a constrained path-existence problem on a grid. For each starting cell matching word[0], run DFS to match the next character. The core invariant is: current DFS state (r, c, i) means we already matched word[0..i] and currently stand at (r, c).
Brute Force and Limitations
A naive idea is to enumerate all possible paths of length L from every cell, then compare strings. That explodes combinatorially. Backtracking prunes immediately on character mismatch and avoids storing all paths.
Optimal Algorithm Steps
1) Loop over every cell as a potential start.
2) If first char matches, DFS with index i=0.
3) On each DFS step, reject out-of-bound or mismatch states.
4) If i == word.length() - 1, return true.
5) Mark current cell as visited (temporary sentinel), explore 4 neighbors, then restore cell (backtrack).
6) If any start succeeds, return true; else false.
Complexity Analysis
Let m,n be board size and L be word length. Worst-case time complexity is O(m*n*4*3^(L-1)) (first step up to 4 branches, later at most 3 because we cannot go back immediately). Space complexity is O(L) for recursion stack.
Common Pitfalls
- Forgetting to restore visited cell during backtracking.
- Reusing one global visited matrix across different starts without reset.
- Missing boundary checks before reading board cell.
- Returning false too early before exploring all valid neighbors.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
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 (r < 0 || c < 0 || r >= board.length || c >= board[0].length) return false;
if (board[r][c] != word.charAt(i)) return false;
if (i == word.length() - 1) return true;
char tmp = 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] = tmp;
return found;
}
}func exist(board [][]byte, word string) bool {
m, n := len(board), len(board[0])
var dfs func(int, int, int) bool
dfs = func(r, c, i int) bool {
if r < 0 || c < 0 || r >= m || c >= n {
return false
}
if board[r][c] != word[i] {
return false
}
if i == len(word)-1 {
return true
}
tmp := 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] = tmp
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 {
public:
bool exist(vector<vector<char>>& board, string word) {
int m = board.size(), n = board[0].size();
function<bool(int,int,int)> dfs = [&](int r, int c, int i) {
if (r < 0 || c < 0 || r >= m || c >= n) return false;
if (board[r][c] != word[i]) return false;
if (i == (int)word.size() - 1) return true;
char tmp = board[r][c];
board[r][c] = '#';
bool 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] = tmp;
return found;
};
for (int r = 0; r < m; r++) {
for (int 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 r < 0 or c < 0 or r >= m or c >= n:
return False
if board[r][c] != word[i]:
return False
if i == len(word) - 1:
return True
tmp = 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] = tmp
return found
for r in range(m):
for c in range(n):
if dfs(r, c, 0):
return True
return Falsevar exist = function(board, word) {
const m = board.length;
const n = board[0].length;
const dfs = (r, c, i) => {
if (r < 0 || c < 0 || r >= m || c >= n) return false;
if (board[r][c] !== word[i]) return false;
if (i === word.length - 1) return true;
const tmp = 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] = tmp;
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;
};中文
题目概述
给定一个字符网格 board 和字符串 word，判断是否存在一条路径按顺序拼出该单词。每步只能上下左右移动，同一个格子在同一路径中最多使用一次。
核心思路
这是一个网格路径匹配问题。枚举起点后做回溯 DFS，状态为 (r, c, i)：表示当前位于 (r,c)，并且已经匹配到 word[i]。下一步去四个方向找 word[i+1]。
暴力解法与不足
暴力方法是从每个格子出发枚举所有长度为 L 的路径再比较字符串，复杂度非常高。回溯法在字符不匹配时立刻剪枝，且不需要存储全部路径。
最优算法步骤
1）遍历每个格子作为起点。
2）当前字符匹配时进入 DFS。
3）若越界或字符不匹配，立即返回 false。
4）若匹配到最后一个字符，返回 true。
5）临时标记当前格子为已访问，递归四邻域，返回前恢复原字符（回溯）。
6）任一起点找到可行路径即 true，否则 false。
复杂度分析
设网格大小为 m*n，单词长度为 L。最坏时间复杂度为 O(m*n*4*3^(L-1))；递归栈空间复杂度为 O(L)。
常见陷阱
- 回溯结束后忘记恢复网格字符。
- 对不同起点复用访问状态但未清理。
- 先访问数组再做边界判断，导致越界。
- 某个方向失败就提前返回，漏掉其他方向。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
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 (r < 0 || c < 0 || r >= board.length || c >= board[0].length) return false;
if (board[r][c] != word.charAt(i)) return false;
if (i == word.length() - 1) return true;
char tmp = 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] = tmp;
return found;
}
}func exist(board [][]byte, word string) bool {
m, n := len(board), len(board[0])
var dfs func(int, int, int) bool
dfs = func(r, c, i int) bool {
if r < 0 || c < 0 || r >= m || c >= n {
return false
}
if board[r][c] != word[i] {
return false
}
if i == len(word)-1 {
return true
}
tmp := 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] = tmp
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 {
public:
bool exist(vector<vector<char>>& board, string word) {
int m = board.size(), n = board[0].size();
function<bool(int,int,int)> dfs = [&](int r, int c, int i) {
if (r < 0 || c < 0 || r >= m || c >= n) return false;
if (board[r][c] != word[i]) return false;
if (i == (int)word.size() - 1) return true;
char tmp = board[r][c];
board[r][c] = '#';
bool 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] = tmp;
return found;
};
for (int r = 0; r < m; r++) {
for (int 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 r < 0 or c < 0 or r >= m or c >= n:
return False
if board[r][c] != word[i]:
return False
if i == len(word) - 1:
return True
tmp = 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] = tmp
return found
for r in range(m):
for c in range(n):
if dfs(r, c, 0):
return True
return Falsevar exist = function(board, word) {
const m = board.length;
const n = board[0].length;
const dfs = (r, c, i) => {
if (r < 0 || c < 0 || r >= m || c >= n) return false;
if (board[r][c] !== word[i]) return false;
if (i === word.length - 1) return true;
const tmp = 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] = tmp;
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;
};
Comments