首尾字符相接的字符串序列(单词接龙)
哪些公司问过
答案要点
- 字符串视为有向边:首字符指向尾字符,节点为字符
- 任意一条可行序列:DFS 回溯,标记已用并在失败时撤销
- 最短序列:BFS 并记录前驱
- 必须用完所有字符串:转化为欧拉路径,用 Hierholzer 算法
- 先明确能否重复使用、是否要求最短或用尽
易错点
- 把字符串当节点建图,边数变成平方级
- 回溯时没有撤销已用标记
- 没有确认字符串能否重复使用就开始写代码
面试官常见追问
- 欧拉路径存在的条件是什么?
- 起始字符等于结束字符时要注意什么?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。