Minimum Genetic Mutation

LC 433, 与word ladder 1 一摸一样

A gene string can be represented by an 8-character long string, with choices from "A", "C", "G", "T".

Suppose we need to investigate about a mutation (mutation from "start" to "end"), where ONE mutation is defined as ONE single character changed in the gene string.

For example, "AACCGGTT" -> "AACCGGTA" is 1 mutation.

Also, there is a given gene "bank", which records all the valid gene mutations. A gene must be in the bank to make it a valid gene string.

Now, given 3 things - start, end, bank, your task is to determine what is the minimum number of mutations needed to mutate from "start" to "end". If there is no such a mutation, return -1.

class Solution {
    public int minMutation(String start, String end, String[] bank) {
        if (bank == null || bank.length == 0 || start.length() != end.length()) return -1;
        Set<String> bankSet = new HashSet<String>(Arrays.asList(bank));
        if (!bankSet.contains(end)) return -1;
        Set<String> visited = new HashSet<>();
        Queue<String> queue = new LinkedList<>();
        queue.offer(start);
        visited.add(start);
        int count = 1;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                String cur = queue.poll();
                Set<String> nextStrings = getNextStrings(cur, bankSet);
                for (String a : nextStrings) {
                    if (visited.contains(a)) {
                        continue;
                    }
                    if (a.equals(end)) return count;
                    visited.add(a);
                    queue.offer(a);
                }
            }
            count++;
        }
        return -1;
    }

    private Set<String> getNextStrings(String cur, Set<String> bankSet) {
        Set<String> results = new HashSet<>();
        char[] chars = new char[]{'A', 'C', 'G','T'};
        for (int i = 0; i < cur.length(); i++) {
            for (int j = 0 ; j < chars.length; j++) {
                if (cur.charAt(i) == chars[j]) continue;
                StringBuilder sb = new StringBuilder();
                sb.append(cur.substring(0, i));
                sb.append(chars[j]);
                sb.append(cur.substring(i + 1));
                if (bankSet.contains(sb.toString())) {
                    results.add(sb.toString());
                }
            }
        }
        return results;
    }
}