大家好，我是 @负雪明烛。👈👈 点击关注，优质题解不间断。

题目大意

给出了一个起始基因 start，一个结束基因 end。

问能不能通过变换，每次变化当前基因的一位，并且变化后的这个基因在基因库中的为有效基因，最后变换成为 end。如果可以的话，返回变换的最小次数。如果不可以的话，返回 -1.

解题方法

BFS

基本和 127. Word Ladder 一模一样的，只不过把 26 个搜索换成了 4 个搜索，所以代码只用改变搜索的范围，以及最后的返回值就行了。

很显然这个问题是 BFS 的问题，同样是走迷宫问题的 4 个方向。

分享 BFS 模板：

BFS使用队列，把每个还没有搜索到的点依次放入队列，然后再弹出队列的头部元素当做当前遍历点。

BFS总共有两个模板：

模板一：

如果不需要确定当前遍历到了哪一层，BFS模板如下。

  1. while queue 不空：
  2.     cur = queue.pop()
  3.     if cur 有效且未被访问过：
  4.         进行处理
  5.     for 节点 in cur 的所有相邻节点：
  6.         if 该节点有效：
  7.             queue.push(该节点)

模板二：

如果要确定当前遍历到了哪一层，BFS 模板如下。
这里增加了 level 表示当前遍历到二叉树中的哪一层了，也可以理解为在一个图中，现在已经走了多少步了。size 表示在当前遍历层有多少个元素，也就是队列中的元素数，我们把这些元素一次性遍历完，即把当前层的所有元素都向外走了一步。

  1. level = 0
  2. while queue 不空：
  3.     size = queue.size()
  4.     while (size --) {
  5.         cur = queue.pop()
  6.         if cur 有效且未被访问过：
  7.             进行处理
  8.         for 节点 in cur的所有相邻节点：
  9.             if 该节点有效：
  10.                 queue.push(该节点)
  11.     }
  12.     level ++;

上面两个是通用模板，在任何题目中都可以用，是要记住的！

本题做法

由于本题需要知道变换了多少次，因此需要确定当前遍历到哪一层，故本题中直接套用模板二。

代码总体思路：

  • 利用队列保存有效的字符串
  • 只要队列不空，就持续循环：
    • 记录当前队列的长度，对队列中该长度的字符串逐一遍历：
      • 如果搜索到 end，直接返回当前的步数 step
      • 否则，对当前字符串中的每个字符，都转变成 ACGT四个字符，看新形成的字符串是否遇到过
        • 如果没遇到过，就放入队列之中。
    • 步数 + 1

其中判断字符串是否遇到过，有两种方法：

  • 使用 set 保存所有已经遇到过的字符串；
  • 直接从 bank 中删除已经遇到过的字符串。

Python, C++ 代码如下：

  1. class Solution(object):
  2.     def minMutation(self, start, end, bank):
  3.         """
  4.         :type start: str
  5.         :type end: str
  6.         :type bank: List[str]
  7.         :rtype: int
  8.         """
  9.         bfs = collections.deque()
  10.         bfs.append((start, 0))
  11.         bankset = set(bank)
  12.         while bfs:
  13.             gene, step = bfs.popleft()
  14.             if gene == end:
  15.                 return step
  16.             for i in range(len(gene)):
  17.                 for x in "ACGT":
  18.                     newGene = gene[:i] + x + gene[i+1:]
  19.                     if newGene in bank and newGene != gene:
  20.                         bfs.append((newGene, step + 1))
  21.                         bank.remove(newGene)
  22.         return -1
  1. class Solution {
  2. public:
  3.     int minMutation(string start, string end, vector<string>& bank) {
  4.         unordered_set<string> bank_set(bank.begin(), bank.end());
  5.         queue<string> que;
  6.         que.push(start);
  7.         unordered_set<string> visited;
  8.         visited.insert(start);
  9.         int step = 0;
  10.         while (!que.empty()) {
  11.             int size = que.size();
  12.             for (int i = 0; i < size; ++i) {
  13.                 string cur = que.front(); que.pop();
  14.                 if (cur == end) {
  15.                     return step;
  16.                 }
  17.                 for (char gene : "ACGT") {
  18.                     for (int j = 0; j < cur.size(); ++j) {
  19.                         string next = cur;
  20.                         next[j] = gene;
  21.                         if (bank_set.count(next) && !visited.count(next)) {
  22.                             que.push(next);
  23.                             visited.insert(next);
  24.                         }
  25.                     }
  26.                 }
  27.             }
  28.             step ++;
  29.         }
  30.         return -1;
  31.     }
  32. };
class Solution {
public:
    int minMutation(string start, string end, vector<string>& bank) {
        queue<string> q;
        const int N = start.size();
        q.push(start);
        int step = 0;
        while (!q.empty()) {
            int size = q.size();
            for (int s = 0; s < size; s++) {
                auto cur = q.front(); q.pop();
                if (cur == end) {
                    return step;
                }
                for (int i = 0; i < N; i++) {
                    for (char n : {'A', 'C', 'G', 'T'}) {
                        string next = cur.substr(0, i) + n + cur.substr(i + 1);
                        if (next == cur) continue;
                        for (auto it = bank.begin(); it < bank.end(); ++it) {
                            if (*it == next) {
                                q.push(next);
                                bank.erase(it);
                                break;
                            }
                        }
                    }
                }
            }
            step += 1;
        }
        return -1;
    }
};

复杂度

  • 时间复杂度：$O(N*L)$，其中 433. 最小基因变化 - 图1是 Bank 中的单词个数，433. 最小基因变化 - 图2是基因的长度。
  • 空间复杂度：$O(N)$

    总结

  1. BFS 模板题，而且出现频率挺高的。

我是 @负雪明烛 ，刷算法题 1000 多道，写了 1000 多篇算法题解，收获阅读量 300 万。
关注我，你将不会错过我的精彩动画题解、面试题分享、组队刷题活动，进入主页 @负雪明烛 右侧有刷题组织，从此刷题不再孤单。