vvrf / DSA.log

问题拆解

在字符网格里找一条上下左右相邻的路径，恰好拼出 word，同一个格子在一条路径里不能重复使用。

这是典型的路径搜索：以每个格子为起点尝试匹配 word[0]，匹配上就向四个方向递归匹配下一个字符。因为同一格不能重复用，需要记录当前路径访问过哪些格子——常规做法是开一个 visited 布尔矩阵，进入时标记、回溯时清除。

关键观察有两个。其一，visited 可以省掉：把当前格子临时改成一个不可能出现的字符（比如 '#'），递归返回后再改回原字符，网格自己就是标记。其二，剪枝要放在递归入口处——越界或当前字符与 word[k] 不匹配，立刻返回 false，绝大多数无效分支在第一层就被砍掉了。

回溯的纪律：进入节点时做的任何修改，离开时必须原样撤销——无论这条分支成功还是失败。

原地标记的网格回溯

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 (i < 0 || i >= board.length || j < 0 || j >= board[0].length
            || board[i][j] != word.charAt(k)) {
        return false; // 越界或字符不匹配，立刻剪掉
    }
    if (k == word.length() - 1) return true;
    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] = word.charAt(k); // 回溯时恢复现场
    return found;
}

def exist(board: List[List[str]], word: str) -> bool:
    m, n = len(board), len(board[0])

    def dfs(i: int, j: int, k: int) -> bool:
        if i < 0 or i >= m or j < 0 or j >= n or board[i][j] != word[k]:
            return False  # 越界或字符不匹配，立刻剪掉
        if k == len(word) - 1:
            return True
        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] = word[k]  # 回溯时恢复现场
        return found

    return any(dfs(i, j, 0) for i in range(m) for j in range(n))

func exist(board [][]byte, word string) bool {
    m, n := len(board), len(board[0])
    var dfs func(i, j, k int) bool
    dfs = func(i, j, k int) bool {
        if i < 0 || i >= m || j < 0 || j >= n || board[i][j] != word[k] {
            return false // 越界或字符不匹配，立刻剪掉
        }
        if k == len(word)-1 {
            return true
        }
        board[i][j] = '#' // 原地标记，防止本条路径重复使用
        found := dfs(i+1, j, k+1) || dfs(i-1, j, k+1) ||
            dfs(i, j+1, k+1) || dfs(i, j-1, k+1)
        board[i][j] = word[k] // 回溯时恢复现场
        return found
    }
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if dfs(i, j, 0) {
                return true
            }
        }
    }
    return false
}

pub fn exist(board: Vec<Vec<char>>, word: String) -> bool {
    fn dfs(board: &mut Vec<Vec<char>>, word: &[char], i: i32, j: i32, k: usize) -> bool {
        let (m, n) = (board.len() as i32, board[0].len() as i32);
        if i < 0 || i >= m || j < 0 || j >= n || board[i as usize][j as usize] != word[k] {
            return false; // 越界或字符不匹配，立刻剪掉
        }
        if k == word.len() - 1 {
            return true;
        }
        let (ui, uj) = (i as usize, j as usize);
        board[ui][uj] = '#'; // 原地标记，防止本条路径重复使用
        let 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[ui][uj] = word[k]; // 回溯时恢复现场
        found
    }

    let mut board = board;
    let word: Vec<char> = word.chars().collect();
    for i in 0..board.len() {
        for j in 0..board[0].len() {
            if dfs(&mut board, &word, i as i32, j as i32, 0) {
                return true;
            }
        }
    }
    false
}

最容易错的地方在恢复现场：board[i][j] = word[k] 要无条件执行，不管这条分支成没成功。本题里“成功后不恢复”碰巧无害——找到后会层层直接返回——但只要题目要求枚举所有解或继续搜索，漏恢复就是脏数据；把“改与还”写成成对的固定动作，不要依赖运气。另外入口检查的顺序也有讲究：越界判断必须放在字符比较之前，否则 Python 里 board[-1][j] 这样的负下标不报错却语义全错，比数组越界异常隐蔽得多。

Rust 版用 i32 做行列坐标，是为了让 i - 1 在边界处不会触发 usize 下溢，越界统一交给入口检查处理。

复杂度

指标	复杂度	原因
时间	`O(m·n·3^L)`	每个格子都可能是起点；路径上除第一步外最多三个方向（不走回头路），L 为单词长度
空间	`O(L)`	递归栈深度即已匹配长度，没有额外标记数组

可以迁移的模式

网格路径搜索的标准骨架：入口统一处理越界与不匹配，四方向递归，进出成对地标记与恢复；
状态能原地改就原地改，省一份 visited 空间，但必须保证“改与还”成对出现；
剪枝放得越早越好：在递归入口一行返回，比展开四个方向前各判一次干净得多。

回溯题的正确性往往不难，难在任何一条返回路径都不能漏掉恢复现场。