题解 | #基因变异最小次数#

知识点

哈希，队列

解题思路

使用set来存放bank数组，队列来存放每一轮遍历的字符串。

遍历队列中的字符串，每次替换字符串中的一个字符，看是否在set中。

如果在set中表示可以继续修改，存放在队列中，此个字符串使用移除set中相应字符串。

当替换之后发现字符串与end相同则返回遍历队列的次数。

Java题解

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param start string字符串 
     * @param end string字符串 
     * @param bank string字符串一维数组 
     * @return int整型
     */
    public int minMutation (String start, String end, String[] bank) {
        // write code here
        int n = start.length(), m = end.length();
        Set<String> set = new HashSet<>(Arrays.asList(bank));
        if(!set.contains(end) || n != m){
            return -1;
        }
        char[] charArr = new char[]{'A','C','G','T'};
        Deque<String> deque = new LinkedList<>();
        deque.offerFirst(start);
        int ans = 0;
        while(!deque.isEmpty()){
            ans ++;
            int size = deque.size();
            for (int i = 0; i < size; i++){
                String s = deque.pollLast();
                char[] sChar = s.toCharArray();
                for(int j = 0; j < s.length(); j++){
                    char oldChar = sChar[j];
                    for(int l = 0; l < 4; l++){
                        if(charArr[l] == oldChar){
                            continue;
                        }
                        sChar[j] = charArr[l];
                        String newS = new String(sChar);
                        if(newS.equals(end)){
                            return ans;
                        }
                        if(set.contains(newS)){
                            deque.offerFirst(newS);
                            set.remove(newS);
                        }
                    }
                    sChar[j] = oldChar;
                }

            }

        }
        return -1;
    }
}