leetcode433-Minimum-Genetic-Mutation

jiezi

5 年前

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

Suppose we need to investigate about a mutation (mutation from "start" to "end"), where ONE mutation is defined as ONE single character changed in the gene string.

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

Also, there is a given gene "bank", which records all the valid gene mutations. A gene must be in the bank to make it a valid gene string.

Now, given 3 things - start, end, bank, your task is to determine what is the minimum number of mutations needed to mutate from "start" to "end". If there is no such a mutation, return -1.

Note:

Starting point is assumed to be valid, so it might not be included in the bank.
If multiple mutations are needed, all mutations during in the sequence must be valid.
You may assume start and end string is not the same.
 

Example 1:

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

return: 1
 

Example 2:

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

return: 2
 

Example 3:

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

return: 3

假设现在有两个基因序列，并且用一个字符串数组 bank 来表示一个基因序列银行。已知每一步可以将当前基因序列中的一位进行改变，变成另一个已知的基因序列。问最少需要多少步可以将初始的基因序列转化为目标基因序列。如果无法转换，则返回 -1。

其实这题是是一个典型的广度优先算法的题目。广度优先遍历通常用于寻找最短路径，将起始基因视作起点，将目标基因视作终点，而一个基因与另一个基因之间是否是相邻节点，则可以通过这两个基因之间是否只相差一个基因位进行判断。为了减少重复的遍历，每经过一个基因序列，就会将它标记为已达。代码如下：

    public int minMutation(String start, String end, String[] bank) {Queue<String> queue = new LinkedList<>();
        Set<String> bankSet = new HashSet<String>();
        for(String item : bank) {bankSet.add(item);
        }
        
        int round = 0;
        queue.add(start);
        while(!queue.isEmpty()) {int numberOfGenes = queue.size();
            while(numberOfGenes-- > 0){String tmp = queue.poll();
                if(tmp.equals(end)) {return round;}
                Iterator<String> iterator = bankSet.iterator();
                while(iterator.hasNext()) {String cur = iterator.next();
                    int count = 0;
                    for(int i = 0 ; i<start.length() ; i++) {char c1 = tmp.charAt(i);
                        char c2 = cur.charAt(i);
                        if(c1 != c2 && ++count > 1) {break;}
                    }
                    if(count == 1) {queue.offer(cur);
                        iterator.remove();}
                }
            }
            round++;
        }
        return -1;
    }

对技术感兴趣的同学，欢迎加博主的微信 RALE_DONG，一起学习共同进步

leetcode433-Minimum-Genetic-Mutation

题目要求

思路和代码