题目分析
这个题目在前几天讲解过,是Leetcode126和Leetcode127题的姐妹题,当时讲解的是第127题求最短的转换序列长度,当时的最优算法是BFS,原因也经常叙述了,找到最近的一条就是BFS,找到任意一条就是DFS,在这里是求任意一条,因此最优解也非常明显,小伙伴们先尝试去做。
DFS
当列表单词很多的时候,我们可以枚举单词的位置,枚举每个位置的字符,假如有字典中10000个单词,每个单词长度为10。如果我们逐一和所有单词比较是否相差一个字符,就需要10000次比较,如果只是枚举长度和可能出现的单词,只需要枚举10*26=260次。这个技巧在处理字符串问题时非常重要,希望小伙伴们务必掌握它。
我们对单词列表进行深搜,当搜索到了则返回true,否则将该点加入visited并且返回false。加入visited的目的是剪枝,防止通过其他的路径再次到达该点进行搜索。
算法的时间复杂度为$O(mn)$,空间复杂度为$O(mn)$,其中n为字典中单词的个数,m为每个单词的长度。
1 | #include<iostream> |
BFS
我们对单词列表进行广搜,当搜索到了直接return即可,否则将该点加入visited并且继续搜索。加入visited的目的也是剪枝,防止通过其他的路径再次到达该点进行搜索。
我在这个算法中每一次搜索都保存了所有的路径,因此空间复杂度为$O(mn^2)$。
可以使用哈希表记录最先到达某点的路径,这样可以追溯求出路径,这样只适合于求最短路径,并不是这类问题的通解。如果要求出所有路径,就无法做到了。所有有兴趣的小伙伴可以尝试去做。
算法的时间复杂度为$O(mn^2)$,空间复杂度为$O(mn)$,其中n为字典中单词的个数,m为每个单词的长度。
1 | #include<iostream> |
刷题总结
搜索类的题目在面试中遇到的并不多,但是在笔试中是非常非常重要的考点,希望小伙伴们可以加强练习,认真准备,争取笔试全AC。