[数据结构与算法]BFS广度有线搜索 LeetCode-433

例题1（LeetCode 433）

解题思路：
因为从start到end过程中，每次基因变化都得是基因库bank里面存在的基因,如上面示例2：
AACCGGTT 变到 AAACGGTA：AACCGGTT----AACCGGTA----AACCGGTA;
经历了两次基因变化，变化过程中的AACCGGTA、AACCGGTA都是基因库中有的。
求最少的变化次数则考虑用广度优先搜索。
步骤
1.首先判断start是否等于end；基因库中是否存在end；
2.遍历基因库bank，把与start相差一个字符的（因为一次只能改变一个字符）且没有访问过的序列入队；
3.一直搜索直到找到等于end的序列

class Solution {
    public int minMutation(String start, String end, String[] bank) {
        Deque<String> queue = new ArrayDeque<>();
        Set<String> visited = new HashSet<>();//为避免重复访问，将访问过的放到集合里

        if(!contains(bank, end) && ！start.equals(end))//如果bank中没有end，且start不等于end
            return -1;
        queue.addLast(start);
        visited.add(start);
        int res = 0;
        while(!queue.isEmpty()){
            int sz = queue.size();
            for(int i=0; i<sz; i++){
                String cur = queue.removeFirst();
                //一直搜索直到找到等于end的序列
                if(cur.equals(end))
                    return res;
                
                for(String str : bank){
                //遍历基因库bank，把与start相差一个字符的（因为一次只能改变一个字符）且没有访问过的序列入队；
                    if(canMutate(str, cur) && !visited.contains(str)){
                        queue.addLast(str);
                        visited.add(str);
                    }
                }
            }
            res++;
        }
        return -1;
    }
    public static boolean canMutate(String str, String cur){
        int n = 0;
        for(int i=0; i<8; i++){
            if(str.charAt(i) != cur.charAt(i))
                n++;
        }
        return n == 1;
    }
    public static boolean contains(String[] bank, String end){
        for(String str : bank){
            if(str.equals(end)){
                return true;
            }
        }
        return false;
    }
}