LeetCode433. 最小基因变化

题目描述

本题目来自 LeetCode 上的『433. 最小基因变化』

一组基因序列由8个字符组成。一次基因变化定义为 基因序列中的一个字符 发生变化。
设 bank 中为所有合法的基因变化，求基因 start 到 end 需要经历几次基因变化。

示例 1：

输入：start = “AACCGGTT”, end = “AACCGGTA”, bank = [“AACCGGTA”]

输出：1

示例 2：

输入：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'] 组成

题解—预处理+BFS

我们用 $0,1,2,…$ 为bank 中的基因编号，以这些编号为顶点建无向图，建图规则如下：

如果两个基因序列的距离为1，即两个基因序列只有一个字符不同，那么就在这两个顶点之间加上一条边。
为了方便搜索，我们将基因序列 start 也加入到 bank 的末尾。

建图完毕后，问题就转化成求 start 所在点 x 到 end 所在点 y 之间的最小距离，如果两点不连通就返回 -1。
无权值图的单源最短路径可以使用 BFS。

代码

class Solution {
private:
    vector<vector<int>> graph;
    int distance(const string& s1, const string& s2) {
        int dist = 0;
        for (int i = 0; i < (int)s1.size(); ++i) {
            if (s1[i] != s2[i]) {
                ++dist;
            }
        }
        return dist;
    }
    void build(const vector<string>& bank) {
        int n = bank.size();
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if (distance(bank[i], bank[j]) == 1) {
                    graph[i].emplace_back(j);
                    graph[j].emplace_back(i);
                }
            }
        }
    }

    int bfs(int x, int y, int n) {
        vector<bool> visited(n, false);
        queue<int> q;
        q.emplace(x);
        visited[x] = true;
        int ans = 0;
        while (!q.empty()) {
            for (int i = q.size(); i > 0; --i) {
                int poll = q.front();
                q.pop();
                if (poll == y) {
                    return ans;
                }
                for (const auto& v : graph[poll]) {
                    if (!visited[v]) {
                        q.emplace(v);
                        visited[v] = true;
                    }
                }
            }
            ++ans;
        }
        return -1;
    }

public:
    int minMutation(string start, string end, vector<string>& bank) {
        bank.emplace_back(start);
        int n = bank.size();
        graph.resize(n);
        build(bank);
        int idx = -1;
        for (int i = 0; i < n; ++i) {
            if (bank[i] == end) {
                idx = i;
                break;
            }
        }
        return bfs(n - 1, idx, n);
    }
};