LeetCode 题解:433. 最小基因变化,BFS,JavaScript,详细注释
原题链接:https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof/
解题思路:
理解题意:
* 该题要求从bank中查找基因从start变化到end的最小次数。
* 基因每次只能变化一个字符。
* 变化的路径不是唯一的。
使用BFS:
* 使用队列进行遍历,队列中按顺序存储了每一层的元素。
* 每次循环时,将队列中当前层的元素依次取出,然后在bank中查找只变化一次的基因序列,将其作为下一层遍历的元素,再放入队列中。
* 对于bank中已被使用的元素,需要用Set缓存,避免重复使用。
* 由于BFS是逐层进行遍历,一旦遇到有序列与目标序列相等,即为找到了最小变化次数,可以退出循环。
重要的Case:
版权声明: 本文为 InfoQ 作者【Lee Chen】的原创文章。
原文链接:【http://xie.infoq.cn/article/51b5d0a0f8d87bd16da6111c0】。文章转载请联系作者。
评论