433. Minimum Genetic Mutation

[Shawngbk]

每次start变化之后都要在bank里面！！！

public class Solution { public int minMutation(String start, String end, String[] bank) { if(start.equals(end)) return 0;

    Set<String> bankSet = new HashSet<>();
    for(String b: bank) bankSet.add(b);

    char[] charSet = new char[]{'A', 'C', 'G', 'T'};
    Queue<String> que = new LinkedList<String>();
    Set<String> set = new HashSet<String>();
    que.offer(start);
    set.add(start);
    int level = 0;
    while(!que.isEmpty()) {
        int size = que.size();
        while(size-- > 0) {
            String curr = que.poll();
            if(curr.equals(end))
            return level;
            char[] currArray = curr.toCharArray();
            for(int i = 0; i < currArray.length; i++) {
                char old = currArray[i];
                for(char c : charSet) {
                    currArray[i] = c;
                    String temp = new String(currArray);
                    if(!set.contains(temp) && bankSet.contains(temp)) {
                        set.add(temp);
                        que.offer(temp);
                    }
                }
                currArray[i] = old;
            }
        }
        level++;
    }
    return -1;
}

}

[Shawngbk]

twitter