题目描述

一条基因序列由一个带有 8 个字符的字符串表示，其中每个字符都属于 "A", "C", "G", "T" 中的任意一个。

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

例如，基因序列由 "AACCGGTT" 变化至 "AACCGGTA" 即发生了一次基因变化。

与此同时，每一次基因变化的结果，都需要是一个合法的基因串，即该结果属于一个基因库。

现在给定 3 个参数 — start, end, bank，分别代表起始基因序列，目标基因序列及基因库，请找出能够使起始基因序列变化为目标基因序列所需的最少变化次数。如果无法实现目标变化，请返回 -1。

样例

start: "AACCGGTT"
end:   "AACCGGTA"
bank: ["AACCGGTA"]

返回值: 1

start: "AACCGGTT"
end:   "AAACGGTA"
bank: ["AACCGGTA", "AACCGCTA", "AAACGGTA"]

返回值: 2

start: "AAAAACCC"
end:   "AACCCCCC"
bank: ["AAAACCCC", "AAACCCCC", "AACCCCCC"]

返回值: 3

注意

• 起始基因序列默认是合法的，但是它并不一定会出现在基因库中。
• 所有的目标基因序列一定是合法的。
• 假定起始基因序列与目标基因序列是不一样的。

算法

(宽度优先搜索 / BFS) $O(n^2 4^n)$

1. 比较基础的宽搜，将每个字符串视为点，字符串之间的变化关系看做边。这相当于求出发点到终点的最短距离，且经过点的必须是合法的。

时间复杂度

• 设字符串的长度为 $n$，最多共有 $O(4^n)$ 个合法的点，边的个数为 $O(n4^n)$，每次转移需要 $O(n)$ 的时间判断是否合法，故总时间复杂度为 $O(n^2 4^n)$。

空间复杂度

• 需要 $O(n4^n)$ 的空间存储队列，距离等数据结构。

C++ 代码

class Solution {
public:
    int minMutation(string start, string end, vector<string>& bank) {
        queue<string> q;
        unordered_map<string, int> dis;
        unordered_set<string> valid(bank.begin(), bank.end());
        const string candidate = "ACGT";

        q.push(start);
        dis[start] = 0;
        while (!q.empty()) {
            string u = q.front();
            q.pop();
            if (u == end) break;

            for (int i = 0; i < u.size(); i++) {
                string v(u);
                for (char c : candidate) {
                    v[i] = c;
                    if (valid.find(v) != valid.end() && dis.find(v) == dis.end()) {
                        dis[v] = dis[u] + 1;
                        q.push(v);
                    }
                }
            }
        }

        if (dis.find(end) == dis.end())
            return -1;
        return dis[end];
    }
};