浅析：最小基因变化

433. 最小基因变化

本篇文章简单分析一下题目 最小基因变化，这个题目是一个 BFS 的模版题，和题目 打开转盘锁 很相似，详情可见 BFS 算法框架

下面从两个不同的角度分析本题：「单向 BFS」「双向 BFS」

单向 BFS

我们以start作为第 0 层，bank中在start基础上改变一位基因作为第 1 层，依次类推，直到寻找到目标基因

同时，我们需要记录bank中基因的访问情况

下面给出对应的代码：

xxxxxxxxxx
public int minMutation(String start, String end, String[] bank) {
    // 转化成 set 方便查找
    Set<String> bankSet = new HashSet<>(Arrays.asList(bank));
    // 边界处理：如果 end 不在 bank 中
    if (!bankSet.contains(end)) return -1;
    // 记录基因访问情况
    Set<String> used = new HashSet<>();
    Queue<String> q = new LinkedList<>();
    q.offer(start);
    used.add(start);
    int count = 0;
    while (!q.isEmpty()) {
        int size = q.size();
        for (int i = 0; i < size; i++) {
            String cur = q.poll();
            // 如果找到，返回步数
            if (cur.equals(end)) return count;
            for (String gene : bankSet) {
                // 从 bank 中去找与当前基因只发生一位改变的基因
                if (!used.contains(gene) && isChangeOne(cur, gene)) {
                    q.offer(gene);
                    // 标记
                    used.add(gene);
                }
            }
        }
        count++;
    }
    return -1;
}
// 判断两个基因是否只有一位不同
private boolean isChangeOne(String source, String target) {
    int changeCount = 0;
    for (int i = 0; i < 8; i++) {
        if (source.charAt(i) != target.charAt(i)) changeCount++;
        if (changeCount > 1) return false;
    }
    return changeCount == 1;
}

双向 BFS

这个题目也符合「双向 BFS」的适用情况，即终点是明确的

xxxxxxxxxx
public int minMutation(String start, String end, String[] bank) {
    Set<String> bankSet = new HashSet<>(Arrays.asList(bank));
    if (!bankSet.contains(end)) return -1;
    Set<String> used = new HashSet<>();
    Set<String> q1 = new HashSet<>();
    Set<String> q2 = new HashSet<>();
    q1.add(start);
    q2.add(end);
    int count = 0;
    while (!q1.isEmpty() && !q2.isEmpty()) {
        Set<String> temp = new HashSet<>();
        for (String cur : q1) {
            if (q2.contains(cur)) return count;
            // 标记
            used.add(cur);
            for (String gene : bankSet) {
                // isChangeOne() 同上
                if (!used.contains(gene) && isChangeOne(cur, gene)) {
                    temp.add(gene);
                }
            }
        }
        q1 = q2;
        q2 = temp;
        count++;
    }
    return -1;
}

这里需要注意的一点，选择恰当标记的时机。不可以在加入队列的时候标记，不然这样一个基因只能加入一端的队列中，这样肯定就无法在一端队列中找到相同的基因 🧬，因为双向队列中的基因各不相同

下面给出错误的代码，加以警示！！

xxxxxxxxxx
// 标记
// used.add(cur);
for (String gene : bankSet) {
    // isChangeOne() 同上
    if (!used.contains(gene) && isChangeOne(cur, gene)) {
        temp.add(gene);
        // 错误标记时机
        used.add(gene);
    }
}