433. 最小基因变化

示例1:
碎碎念
解析
如何下手？
我的武器在那里？
具体？
代码
杂谈
碎碎话

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

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

例如，"AACCGGTT" --> "AACCGGTA" 就是一次基因变化。
另有一个基因库bank记录了所有有效的基因变化，只有基因库中的基因才是有效的基因序列。

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

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

示例1:

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

篇幅有限，这里只给出一个示例。

碎碎念

今天是2022年的5月7日，在此日的0点，看过了这题，是当日的每日一题，粗略的看了一眼题目，思来想去，横竖无头绪，只在字里行间看到两个字，回溯。思考了一会，发现不止如何下手。遂看题解，由于当时已无心学习，在电子书与力扣反复切换，作罢。这个懒狗居然将疑问抛给早晨后的自己…怎么睡得着的（一大早就被空调冻醒）。

解析

题目的大意是，给定一个初始基因序列start，在符合特定条件的前提下，每次可用修改start的其中的一个字符，直到start与end相等，求最少的更改次数。

特定条件为：

更改的字符必须是 'A'、'C'、'G' 和 'T' 之一。
每一次更改字符后形成的字符串必须存在于bank数组当中。

举个例子：若 start = "AACCGGTT", end = "AACCGGCA", bank = ["AACCGGCA", "AACCGGTA"]，在这个例子当中，修改start字符串并不是 'A'、'C'、'G' 、 'T'中任意一个替换都可以的。我将修改之后的字符串命名为next。那么next必须是bank中的元素。

也就是说，在这个例子下，改法步骤有且仅有两种。

第一步，start = "AACCGGTT" -> next = "AACCGGTA"，而不能 start = "AACCGGTT" -> next = "AACCGGTC" or next = "AACCGGTG"等等，因为"AACCGGTC"与"AACCGGTG"并不是bank中的元素。

同理，第二步就只能是"AACCGGTA" -> "AACCGGCA"。

最终修改次数，即为2。

说到这里，应该大致明了题目意思了。

所以，我应该怎么做？未看题解之前，我完全没有想到，这其实是一个图论问题，抽象出来其实是在求图的最小路径长度。

如何下手？

图的遍历方式有dfs和bfs，这两种都可以解决这个问题，但显然bfs会比较清晰明了。我可用把start与修改的每一个next抽象成一颗N叉树。

举个例子：

若例子为start = "AAAAACCC", end = "AACCCCCC", bank = ["AAAACCCC","AAACCCCC","AACCCCCC", "AAAATCCC"]

那么其结构就是这样：

显然，最小变化次数为3次。

那么利用bfs，我就可用逐层的遍历可能的修改，这样，一旦某一层符合条件的修改字符串等于end，自然而然就找到了最小的修改次数（因为在此之前绝无等于end的情况，我总是逐层遍历的），也就是这颗N叉数的层数。仔细想想，应该没有问题。

我的武器在那里？

首先，若需要快速的知道修改的字符串是否存在与bank中，显然需要一个哈希表。

以及，需要判断修改的字符串是否以及遍历过了，需要有一个visited记录，同样也用哈希表存储。

当然，也要有用于枚举修改可能性的char cells[4] = {'A', 'C', 'G', 'T'};

最后，bfs必备的队列。

具体？

依据题目意思，当初始情况下start若与end相等，则无需做任何处理。直接return 0;

否则，我们需要建立一个哈希表来方便查询字符串是否存在于bank，以及需要维护一个visited记录是否访问过修改的元素。

如果end不存在于bank，那么代表着修改的结果不可能会end相等。

unordered_set<string> cnt; // 用于查询元素是否存在于bank
unordered_set<string> visited; // 记录是否访问过修改的元素。
char cells[4] = {'A', 'C', 'G', 'T'};
for (auto& s : bank) cnt.insert(s); // 将bank中的元素添加到cnt中
if (cnt.count(end) == 0) return -1; // 如果end不存在于bank，那么代表着修改的结果不可能会end相等。

之后，就是进行bfs搜索，一旦遇到修改字符串与end相等的情况，那么就输出当前的层数，否则，当bfs搜索完毕依然未找到结果，则代表bank所给出的路径无法到达end。

代码

class Solution {
public:
    int minMutation(string start, string end, vector<string>& bank) {
        if (start == end) return 0;
        unordered_set<string> cnt; // 用于查询元素是否存在于bank
        unordered_set<string> visited; // 记录是否访问过修改的元素。
        for (auto& s : bank) cnt.insert(s); // 将bank中的元素添加到cnt中
        if (cnt.count(end) == 0) return -1; // 如果end不存在于bank，那么代表着修改的结果不可能会end相等。
        queue<string> q;
        q.push(start);
        visited.insert(start);
        char cells[4] = {'A', 'C', 'G', 'T'};
        int step = 1; // 记录bfs搜索层数
        while (!q.empty()) {
            int size = q.size();
            for (int k = 0; k < size; k++) {
                string node = q.front();
                q.pop();
                for (int i = 0; i < 8; i++) {
                    for (int j = 0; j < 4; j++) {
                        if (node[i] == cells[j]) continue;
                        string next = node;
                        next[i] = cells[j];
                        if (cnt.count(next) && !visited.count(next)) {
                            if (next == end) return step;
                            visited.insert(next);
                            q.push(next);
                        }
                    }
                }
            }
            step++;
        }
        return -1;
    }
};