单词搜索 LC79:DFS 回溯与边界处理
哪些公司问过
答案要点
- dfs(i,j,k) 先判越界、已访问、字符不匹配,再判是否已匹配到最后一个字符
- 进入时标记已访问(原地改特殊字符或 visited 数组),四方向递归后恢复原值完成回溯
- 外层枚举所有起点,任一起点 dfs 成功即返回 true
- 时间约 O(m·n·3^L),空间为递归栈 O(L)
- 可用字符频次剪枝,或按首尾字符稀有度决定是否反转 word
易错点
- 先访问 board[i][j] 再判越界,导致数组越界
- 回溯时忘记恢复格子,其他搜索路径被错误阻断
- 终止条件位置不对,单字符单词或末字符匹配时结果错误
- 使用全局 visited 却在部分返回路径上没有复位
面试官常见追问
- 如果要在同一棋盘中查找多个单词怎么办?
- 不原地修改棋盘可以吗?
- 为什么复杂度是 3^L 而不是 4^L?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。