433. Minimum Genetic Mutation 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class Solution {
    private static final char[] GENES = new char[]{'A', 'C', 'G', 'T'};

    public int minMutation(String startGene, String endGene, String[] bank) {
        Set<String> geneSet = new HashSet<>(Arrays.asList(bank));
        if (startGene.equals(endGene)) {
            return 0;
        }
        if (!geneSet.contains(endGene)) {
            return -1;
        }

        Queue<String> queue = new LinkedList<>();
        queue.offer(startGene);

        int count = 0;
        while (!queue.isEmpty()) {
            for (int i = queue.size(); i > 0; i--) {
                String gene = queue.poll();
                if (endGene.equals(gene)) {
                    return count;
                }

                char[] chars = gene.toCharArray();
                for (int j = 0; j < chars.length; j++) {
                    char sourceChar = chars[j];
                    for (char g : GENES) {
                        if (g == sourceChar) {
                            continue;
                        }

                        chars[j] = g;
                        String nextGene = new String(chars);
                        if (geneSet.contains(nextGene)) {
                            queue.offer(nextGene);
                            geneSet.remove(nextGene);
                        }
                    }
                    chars[j] = sourceChar;
                }
            }

            count++;
        }

        return -1;
    }
}

References

433. Minimum Genetic Mutation