LeetCode 题解:433. 最小基因变化,DFS,JavaScript,详细注释
原题连接:https://leetcode-cn.com/problems/minimum-genetic-mutation/
解题思路:
理解题意:
* 该题要求从bank中查找基因从start变化到end的最小次数。
* 基因每次只能变化一个字符。
* 变化的路径不是唯一的。
使用DFS:
* 每次递归都从bank中选取与当前基因相比,只变化一个字符的基因,将其作为中间结果,进入下层递归。
* 为保证不重复选取bank中的元素,使用Set标识bank中的元素是否被访问过。
* 遇到中间结果与end相等,即为找到一条可能的变化路径。
* 由于路径不止一条,因此变化次数要取最小值。
重要的Case:
版权声明: 本文为 InfoQ 作者【Lee Chen】的原创文章。
原文链接:【http://xie.infoq.cn/article/1349d825626ef58cc53cd96c1】。文章转载请联系作者。
评论