433-最小基因变化(Minimum Genetic Mutation)

原文链接: https://leetcode-cn.com/problems/minimum-genetic-mutation

英文原文

A gene string can be represented by an 8-character long string, with choices from 'A', 'C', 'G', and 'T'.

Suppose we need to investigate a mutation from a gene string start to a gene string end where one mutation is defined as one single character changed in the gene string.

For example, "AACCGGTT" --> "AACCGGTA" is one mutation.

There is also a gene bank bank that records all the valid gene mutations. A gene must be in bank to make it a valid gene string.

Given the two gene strings start and end and the gene bank bank, return the minimum number of mutations needed to mutate from start to end. If there is no such a mutation, return -1.

Note that the starting point is assumed to be valid, so it might not be included in the bank.

Example 1:

Input: start = "AACCGGTT", end = "AACCGGTA", bank = ["AACCGGTA"]
Output: 1

Example 2:

Input: start = "AACCGGTT", end = "AAACGGTA", bank = ["AACCGGTA","AACCGCTA","AAACGGTA"]
Output: 2

Example 3:

Input: start = "AAAAACCC", end = "AACCCCCC", bank = ["AAAACCCC","AAACCCCC","AACCCCCC"]
Output: 3

Constraints:

start.length == 8
end.length == 8
0 <= bank.length <= 10
bank[i].length == 8
start, end, and bank[i] consist of only the characters ['A', 'C', 'G', 'T'].

中文题目

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

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

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

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

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

注意：

起始基因序列默认是合法的，但是它并不一定会出现在基因库中。
如果一个起始基因序列需要多次变化，那么它每一次变化之后的基因序列都必须是合法的。
假定起始基因序列与目标基因序列是不一样的。

示例 1：

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

返回值: 1

示例 2：

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

返回值: 2

示例 3：

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

返回值: 3

通过代码

高赞题解

解题思路：

这是一个很典型的广度优先搜索问题，和之前的单词接龙问题是一样的。
因为是求最短的转换路径问题，那么广度搜索是优于深度搜索的。
这里的做法就是将起点和终点分别加入两个集合当中，然后从集合元素少的一端开始搜索，这样能够减少搜索量，知道两个集合产生了交集，那么就结束了搜索。
各位力扣老爷，公审天皇，走向未曾设想的道路，还请各位立刻捐赠20个赞，以便我军再战。

无记忆化版本（存在问题）


class Solution {

    public int minMutation(String start, String end, String[] bank) {

        // 定义三个集合，分别是合法基因集合，起始基因集合，目标基因集合

        Set<String> dict = new HashSet<>(), st = new HashSet<>(), ed = new HashSet<>();

        for(String s : bank) dict.add(s);

        // 基因库中不包含目标，则无法转换

        if(!dict.contains(end)) return -1;



        st.add(start);

        ed.add(end);

        // 宽搜

        return bfs(st, ed, dict, 0);

    }



    // 宽搜

    private int bfs(Set<String> st, Set<String> ed, Set<String> dict, int len) {

        // 起始集合为空，那么就无法到达目标

        if(st.size() == 0) return -1;

        // 优先从数量少的一端开始搜索，减少搜索量

        if(st.size() > ed.size()) return bfs(ed, st, dict, len);



        Set<String> next = new HashSet<>();

        char[] mode = {'A', 'C', 'G', 'T'};

        // 枚举起始集合可以一步转换的所有基因序列

        for(String s : st) {

            StringBuilder temp = new StringBuilder(s);

            for(int i = 0; i < 8; i++) {

                for(int j = 0; j < 4; j++) {

                    // 不包含相同的字符

                    if(s.charAt(i) == mode[j]) continue;

                    temp.setCharAt(i, mode[j]);

                    String cur = temp.toString();

                    // 终点集合中包含了当前字符，那么直接返回步数

                    if(ed.contains(cur)) return len + 1;

                    // 如果是合法序列，则加入下一个搜索集合中

                    if(dict.contains(cur)) {

                        next.add(cur);

                    }

                    temp.setCharAt(i, s.charAt(i));

                }

            }

        }

        // 搜索下一层

        return bfs(next, ed, dict, len + 1);

    }

}

记忆化版本


class Solution {

    public int minMutation(String start, String end, String[] bank) {

        // 定义三个集合，分别是合法基因集合，起始基因集合，目标基因集合，起始基因记忆集，目标基因记忆集

        Set<String> dict = new HashSet<>(), st = new HashSet<>(), ed = new HashSet<>(), menSt = new HashSet<>(), menEd = new HashSet<>();

        for(String s : bank) dict.add(s);

        // 基因库中不包含目标，则无法转换

        if(!dict.contains(end)) return -1;



        st.add(start);

        ed.add(end);

        // 宽搜

        return bfs(st, ed, menSt, menEd, dict, 0);

    }



    // 宽搜

    private int bfs(Set<String> st, Set<String> ed, Set<String> menSt, Set<String> menEd, Set<String> dict, int len) {

        // 起始集合为空，那么就无法到达目标

        if(st.size() == 0) return -1;

        // 优先从数量少的一端开始搜索，减少搜索量

        if(st.size() > ed.size()) return bfs(ed, st, menEd, menSt, dict, len);



        Set<String> next = new HashSet<>();

        char[] mode = {'A', 'C', 'G', 'T'};

        // 枚举起始集合可以一步转换的所有基因序列

        for(String s : st) {

            StringBuilder temp = new StringBuilder(s);

            for(int i = 0; i < 8; i++) {

                for(int j = 0; j < 4; j++) {

                    temp.setCharAt(i, mode[j]);

                    String cur = temp.toString();

                    // 终点集合中包含了当前字符，那么直接返回步数

                    if(ed.contains(cur)) return len + 1;

                    // 如果搜过了该种情况，就不能重复遍历

                    if(menSt.contains(cur)) continue;     

                    

                    // 如果是合法序列，则加入下一个搜索集合中

                    if(dict.contains(cur)) {

                        next.add(cur);

                        menSt.add(cur);

                    }

                    temp.setCharAt(i, s.charAt(i));

                }

            }

        }

        // 搜索下一层

        return bfs(next, ed, menSt, menEd, dict, len + 1);

    }

}

统计信息

通过次数	提交次数	AC比率
16700	31425	53.1%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言

相似题目

题目	难度
单词接龙	困难

凤起丶宛南

从来没有真正的绝境，只有心灵的迷途