广度优先搜索 | 最小基因变化（433） + 单词接龙（127）

目录

• • 1 433. 最小基因变化
    • • 1.1 代码细节
      • 1.2 完整代码

    • 2 127. 单词接龙

---

前言 ：「433. 最小基因变化」与「127. 单词接龙」这两个问题均可通过构建图结构并采用广度优先搜索的方式加以解决。

1 433. 最小基因变化

解题思路：

• 将某一个基因序列对应为图结构中的一个节点；
• 当两个基因序列具备相互转换的可能性时，在二者之间建立连接边；

进而将该问题转化为：确定从 \mathrm{startGene} 节点至 \mathrm{endGene} 节点的最短路径长度。

思路说明图：

【由题意可知，若两个基因序列之间能够相互转换，则它们之间仅存在一个字符的差异。以基因序列 \mathrm{AACCGGTT} 与基因序列 \mathrm{AACCGGTA} 为例，二者仅在最后一个字符上存在不同，因此具备相互转换的可能性，二者之间应存在连接关系。其余节点的处理方式与此相同。

说明：若基因 $