433. Minimum Genetic Mutation

[3RD TRY]

100.00 %
class Solution {
    public int minMutation(String start, String end, String[] bank) {
        Set<String> bankSet = new HashSet<>(Arrays.asList(bank));
        if (!bankSet.contains(end)) return -1;
        if (start.equals(end)) return 0;
        Set<String> visited = new HashSet<>();
        char[] mutation = new char[]{'A', 'C', 'G', 'T'};
        int level = 0;
        Queue<String> que = new LinkedList<>();
        que.offer(start);
        visited.add(start);
        while (!que.isEmpty()) {
            int size = que.size();
            level++;
            while (size-- > 0) {
                char[] curr = que.poll().toCharArray();
                for (int i = 0; i < curr.length; i++) {
                    char temp = curr[i];
                    for (char m : mutation) {
                        curr[i] = m;
                        String next = new String(curr);
                        // System.out.println(next);
                        if (next.equals(end)) return level;
                        if (bankSet.contains(next) && !visited.contains(next)) {
                            que.offer(next);
                            visited.add(next);
                        }
                    }
                    curr[i] = temp;
                }
               
            }
        }
        return -1;
    }
}

二刷
46.71 %
class Solution {
    public int minMutation(String start, String end, String[] bank) {
        if (start == null || end == null || bank == null) return -1;
        Set<String> hashBank = new HashSet<>();
        for (String str : bank) {
            hashBank.add(str);
        }
        char[] genes = new char[]{'A', 'C', 'G', 'T'};
        Queue<String> que = new LinkedList<>();
        que.offer(start);
        int level = 0;
        while (!que.isEmpty()) {
            level++;
            int size = que.size();
            while (size-- > 0) {
                String curr = que.poll();
                char[] array = curr.toCharArray();
                for (int i = 0; i < array.length; i++) {
                    char prevChar = array[i];
                    for (char gene : genes) {
                        if (gene != prevChar) {
                            array[i] = gene;
                            String neighbor = new String(array);
                            if (hashBank.contains(neighbor)) {
                                if (neighbor.equals(end)) return level;
                                que.offer(neighbor);
                                hashBank.remove(neighbor);
                            }
                        }
                    }
                    array[i] = prevChar;
                }
            }
        }
        return -1;
    }
}
一刷
CharArray Version

Time Level Traverse the graph
#Vertex = bankSize n

each node will be visited at most twice(push into queue, poll out of queue)

Time O(size of bank)

Space queue -> each node has at most 3 children, height at most 8, so 3^8 constant O(1)

下一个直接用substring的特别慢，所以写了一个charArray的，稍微好一点


45.80 %
class Solution {
    public int minMutation(String start, String end, String[] bank) {
        if (start == null || end == null || start.length() != end.length()) return -1;
        if (start.equals(end)) return 0;
        char[] geneSet = new char[]{'A', 'C', 'G', 'T'};
        Set<String> bankSet = new HashSet<>();
        for (String str : bank) bankSet.add(str);
        if (!bankSet.contains(end)) return -1;
     
        Queue<String> que = new LinkedList<>();
        que.offer(start);
        int level = 0;
        String curr = null;
        while(!que.isEmpty()) {
            int size = que.size();
            level++;
            while (size-- > 0) {
                curr = que.poll();
                char[] currArray = curr.toCharArray();
                for (int i = 0; i < currArray.length; i++) {
                    char currChar = currArray[i];
                    for (int j = 0; j < 4; j++) {
                        if (currChar != geneSet[j]) {
                            currArray[i] = geneSet[j];
                            String neighbor = new String(currArray);
                            if (neighbor.equals(end)) return level;
                            if (bankSet.contains(neighbor)) {
                                que.offer(neighbor);
                                bankSet.remove(neighbor);
                            }
                            currArray[i] = currChar;
                        }
                    }
                }
            }
        }
        return -1;
    }
}




4.56 %
class Solution {
    public int minMutation(String start, String end, String[] bank) {
        if (start == null || end == null || start.length() != end.length()) return -1;
        if (start.equals(end)) return 0;
        Set<String> bankSet = new HashSet<>();
        for (String str : bank) {
            bankSet.add(str);
        }
        if (!bankSet.contains(end)) return -1;
     
        Set<Character> geneSet = new HashSet<>();
        geneSet.add('A');
        geneSet.add('C');
        geneSet.add('G');
        geneSet.add('T');
     
        //BFS
        return minMutationBFSHelper(start, end, bankSet, geneSet);
    }
    private int minMutationBFSHelper(String start, String end, Set<String> bankSet, Set<Character> geneSet) {
     
        Queue<String> que = new LinkedList<>();
        que.offer(start);
        String curr = null;
        int level = 0;
        while(!que.isEmpty()) {
            int size = que.size();
            level++;
            while (size-- > 0) {
                curr = que.poll();
                List<String> neighbors = getNeighbors(curr, bankSet, geneSet); // TODO
                //bankSet makes sure that no String can be visited twice
                for (String neighbor : neighbors) {
                    if (neighbor.equals(end)) {
                        return level;
                    } else {
                        que.offer(neighbor);
                    }
                }
            }
         
        }
        return -1;
    }
    private List<String> getNeighbors(String curr, Set<String> bankSet, Set<Character> geneSet) {
        List<String> neighbors = new ArrayList<>();
        for (int i = 0; i < curr.length(); i++) {
            for (Character substitute : geneSet) {
                if (substitute != curr.charAt(i)) {
                    String str = curr.substring(0, i) + substitute + curr.substring(i + 1, curr.length());
                    //System.out.println(str);
                    if (bankSet.contains(str)) {
                        neighbors.add(str);
                        bankSet.remove(str);
                    }
                }
            }
        }
        return neighbors;
    }
}