面试题库 › 嵌入式 › 单词搜索 LC79:DFS 回溯与边界处理

单词搜索 LC79:DFS 回溯与边界处理

难度 ★★☆在 1 场真实面经中被问到 方向:嵌入式考点:贪心与回溯

哪些公司问过

华为1

常见岗位:嵌入式软件

答案要点

  1. dfs(i,j,k) 先判越界、已访问、字符不匹配,再判是否已匹配到最后一个字符
  2. 进入时标记已访问(原地改特殊字符或 visited 数组),四方向递归后恢复原值完成回溯
  3. 外层枚举所有起点,任一起点 dfs 成功即返回 true
  4. 时间约 O(m·n·3^L),空间为递归栈 O(L)
  5. 可用字符频次剪枝,或按首尾字符稀有度决定是否反转 word

易错点

面试官常见追问

完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。

相关面试题