leetcode433 最小基因变化-bfs

红太狼 2023-07-02 05:29 8阅读 0赞

一条基因序列由一个带有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

思路： 之前题目太长了，一下子看糊了，做错了，后来了解到是每次变化都必须按照基因库中的来。否则就淘汰。  
所以bfs。就不断更换每个位置上的AGCT.判断满足吗，满足就结束，若存在基因库，就加入队列。又加深了bfs将问题抽象成图的思路。

class Solution {
        
        public int minMutation(String start, String end, String[] bank) {
        
            HashSet<String> set = new HashSet<>(Arrays.asList(bank));
            if (!set.contains(end))
                return -1;
            char[] c = {
        'A','G','C','T'};
            Queue<String> queue = new LinkedList<>();
            queue.offer(start);
            set.remove(start);
            int step = 0;
            while(!queue.isEmpty()) {
        
                step++;
                for (int i = queue.size();i > 0 ;i--) {
        
                    char[] tmpString = queue.poll().toCharArray();
                    for (int j = 0;j < tmpString.length;j++) {
        
                        char oldChar = tmpString[j];
                        for (int m = 0;m < c.length;m++) {
        
                            tmpString[j] = c[m];
                            String newStr = new String(tmpString);
                            if (end.equals(newStr)) {
        
                                return step;
                            } else if (set.contains(newStr)) {
        
                                set.remove(newStr);
                                queue.offer(newStr);
                            }
                        }
                        tmpString[j] = oldChar;
                    }
                }
            }
            return -1;
        }
    }

技巧2： 双向bfs ，速度将加快。如果每次选择较小的层次将减少多于的搜索。

class Solution {
        
        public int minMutation(String start, String end, String[] bank) {
        
            HashSet<String> set = new HashSet<>(Arrays.asList(bank));
            if (!set.contains(end))
                return -1;
            char[] c = {
        'A','G','C','T'};
            HashSet<String> positive = new HashSet<String>(){
        {
        add(start);}};
            HashSet<String> negetive = new HashSet<String>(){
        {
        add(end);}};
            HashSet<String> tmp = new HashSet<>();
    
           
            int step = 0;
            while (positive.size() > 0 && negetive.size() > 0) {
        
                step++;
    			// 每次换小的
                if (positive.size() > negetive.size()) {
        
                HashSet temp = positive;
                positive = negetive;
                negetive = temp;
                }
    
                for (String str: positive) {
        
                    char[] strc = str.toCharArray();
                    for (int i = 0;i < strc.length;i++) {
        
                        char old = strc[i];
                        for (int j = 0;j < c.length;j++) {
        
                            strc[i] = c[j];
                            String newStr = new String(strc);
                            if (negetive.contains(newStr)) {
          // 判断存在吗
                                return step;
                            } else if (set.contains(newStr)) {
        
                                set.remove(newStr);
                                tmp.add(newStr);
                            }
                        }
                        strc[i] = old;
                    }
                }
                positive = new HashSet<String>(tmp);
                tmp.clear();
            } 
                return -1;
    
        }
    }