最小基因变化

标签: 广度优先搜索哈希表字符串

难度: Medium

基因序列可以表示为一条由 8 个字符组成的字符串，其中每个字符都是 'A'、'C'、'G' 和 'T' 之一。

假设我们需要调查从基因序列 start 变为 end 所发生的基因变化。一次基因变化就意味着这个基因序列中的一个字符发生了变化。

例如，"AACCGGTT" --> "AACCGGTA" 就是一次基因变化。

另有一个基因库 bank 记录了所有有效的基因变化，只有基因库中的基因才是有效的基因序列。（变化后的基因必须位于基因库 bank 中）

给你两个基因序列 start 和 end ，以及一个基因库 bank ，请你找出并返回能够使 start 变化为 end 所需的最少变化次数。如果无法完成此基因变化，返回 -1 。

注意：起始基因序列 start 默认是有效的，但是它并不一定会出现在基因库中。

示例 1：

输入：start = "AACCGGTT", end = "AACCGGTA", bank = ["AACCGGTA"]
输出：1

示例 2：

输入：start = "AACCGGTT", end = "AAACGGTA", bank = ["AACCGGTA","AACCGCTA","AAACGGTA"]
输出：2

示例 3：

输入：start = "AAAAACCC", end = "AACCCCCC", bank = ["AAAACCCC","AAACCCCC","AACCCCCC"]
输出：3

提示：

start.length == 8
end.length == 8
0 <= bank.length <= 10
bank[i].length == 8
start、end 和 bank[i] 仅由字符 ['A', 'C', 'G', 'T'] 组成

Submission

运行时间: 21 ms

内存: 16.2 MB

class Solution:
    def minMutation(self, startGene: str, endGene: str, bank: List[str]) -> int:
        # 所有target必须在bank里
        if endGene not in bank:
            return -1
        
        ans = 10
        if startGene not in bank:
            bank.append(startGene)

        # 建立邻接矩阵, i-j是否是一次基因变化
        n = len(bank)
        edge = [[0 for j in range(n)] for i in range(n)]
        for i in range(n):
            for j in range(i + 1, n):
                cnt = 0
                for k in range(8):
                    if bank[i][k] != bank[j][k]:
                        cnt += 1 
                if cnt == 1:
                    edge[i][j] = edge[j][i] = 1 
        
        vis = [False for i in range(n)]
        vis[bank.index(startGene)] = True
        def dfs(gene, cur):
            nonlocal ans, vis
            # base case
            if gene == endGene:
                ans = min(ans, cur)
                return

            # 向着所有可能的方向前进
            for i in range(n):
                if not vis[i] and edge[bank.index(gene)][i] == 1:
                    vis[i] = True
                    dfs(bank[i], cur + 1)
                    vis[i] = False
            

        dfs(startGene, 0)

        if ans == 10:
            return -1 
        return ans

Explain

这个题解采用深度优先搜索的方法来寻找从起始基因序列到目标基因序列的最短变化路径。首先判断目标基因序列是否在基因库中，如果不在则直接返回-1。然后构建一个邻接矩阵表示基因库中每两个基因序列之间是否只差一个字符。接着从起始基因序列开始进行深度优先搜索，每次变化一个字符，搜索所有可能的变化路径，同时记录变化的次数，找到最短的变化路径。

时间复杂度: O(n^2)

空间复杂度: O(n^2)

class Solution:
    def minMutation(self, startGene: str, endGene: str, bank: List[str]) -> int:
        # 所有target必须在bank里
        if endGene not in bank:
            return -1
        
        ans = 10
        if startGene not in bank:
            bank.append(startGene)

        # 建立邻接矩阵, i-j是否是一次基因变化
        n = len(bank)
        edge = [[0 for j in range(n)] for i in range(n)]
        for i in range(n):
            for j in range(i + 1, n):
                cnt = 0
                for k in range(8):
                    if bank[i][k] != bank[j][k]:
                        cnt += 1 
                if cnt == 1:
                    edge[i][j] = edge[j][i] = 1 
        
        vis = [False for i in range(n)]
        vis[bank.index(startGene)] = True
        def dfs(gene, cur):
            nonlocal ans, vis
            # base case，找到目标基因序列
            if gene == endGene:
                ans = min(ans, cur)
                return

            # 向着所有可能的方向前进，遍历所有相邻的基因序列
            for i in range(n):
                if not vis[i] and edge[bank.index(gene)][i] == 1:
                    vis[i] = True
                    dfs(bank[i], cur + 1)
                    vis[i] = False
            

        dfs(startGene, 0)

        if ans == 10:
            return -1 
        return ans

Explore

这种方法的目的是识别两个基因序列是否可以通过单一字符的变化相互转换，这是题目要求的基因变化的定义。如果两个序列之间恰好有一个字符不同，就表示它们可以直接通过一步的突变相互转换。这种只计算字符差异数量并判断是否为1的方式，是一种准确且直接的方法来实现这个目标。这样可以确保构建的邻接矩阵准确反映出基因序列间的单步变化可能性。

在深度优先搜索（DFS）中，递归方法因其直观和简洁而常常被选择，尤其是在处理复杂的树形或图形结构时。递归允许程序自然地回溯到之前的状态，这在DFS中非常重要。然而，递归可能导致大量的堆栈使用，特别是在深度很大或搜索空间很广的情况下，可能会导致性能问题或堆栈溢出。迭代方法虽然可以避免堆栈溢出的问题，但通常会使代码更加复杂，需要手动管理栈来保存状态。对于本题的基因变化路径搜索，递归的方法提供了足够的简洁性和直观性，对于算法的理解和实现都较为有利。

变量`ans`初始化为10的原因可能是假设在最坏的情况下，基因序列的改变次数不会超过基因长度（这里为8），或者考虑到某些边界情况下改变次数略多于基因长度。这个值作为一个比较大的初始最小值，用来确保能够通过比较找到实际的最小变化次数。更好的初始化方式可以是设置为一个比题目限制还要大的值，比如`float('inf')`，这样可以避免对特定题目的假设，使代码更具一般性和可扩展性。

如果`startGene`等于`endGene`，理论上不需要任何变化就已经达到了目标序列。在题解中，这种情况会在DFS开始时直接被处理，因为递归的基本情况是检查当前基因序列是否等于目标序列。如果在一开始调用DFS时`startGene`与`endGene`相等，递归将在首次检查时满足基本情况，返回变化次数0。因此，题解已经隐含地处理了这种特殊情况。