和127. Word Ladder很像，顺便一起做了

https://leetcode.com/problems/word-ladder/description/

Word Ladder

• 将每个单词看成是一个节点
• 如果存在只转换一个字母就可以完成的转换，看作节点间有通路；
• 给定s1 to s2则可看作为求两点间最短距离问题

由于是unweighted的图所以直接bfs就可以了用不到Dijkstra

代码思路

用两个set： beginset 和endset，理论上应该有一个visited set 但是这个可以用wordList代替，visited了就remove掉

初始里面begin有begin endset里面有end

然后一直找begin的neighbor，用neighbor set 存，这里的思路是word的每个位置都换成a-z

因为每次循环的时间复杂度都是#beginset x word length x 26 所以每次结束后看情况调换一下end 和 begin

Minimum Genetic Mutation

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

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

        Set<String> dict = new HashSet<>();
        for(int i=0;i<bank.length;i++){
            dict.add(bank[i]);
        }
        Set<String> startSet = new HashSet<>();
        Set<String> endSet = new HashSet<>();

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

        startSet.add(start);
        endSet.add(end);

        int count =0;

        while(!startSet.isEmpty()&&!endSet.isEmpty()){
            Set<String> neighborSet = new HashSet<>();
            for (String S: startSet){
                for (int i=0;i<S.length();i++){
                    char []chars= S.toCharArray();
                    for(int j=0;j<GENE.length;j++){
                        chars[i]=GENE[j];
                        String tmp = String.valueOf(chars);
                        if(endSet.contains(tmp)) {return count+1;}
                        if (dict.contains(tmp)){
                            neighborSet.add(tmp);
                            dict.remove(tmp);
                        }

                    }chars=S.toCharArray();
                }

            }count++;

            if (neighborSet.size()<endSet.size()){
                startSet=neighborSet;
            }else{
                startSet=endSet;
                endSet=neighborSet;
            }
        }

        return -1;


    }
}