# 433. Minimum Genetic Mutation

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LekNH5IywF8mjBxFcnu%2F-Mdu45OeF6dx9D7QIZtZ%2F-Mdu4Wu4NfKdVCF2X5lz%2Fimage.png?alt=media\&token=6c963dbd-b050-4955-b904-8bdba3305016)

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LekNH5IywF8mjBxFcnu%2F-Mdu45OeF6dx9D7QIZtZ%2F-Mdu4agE3S30Kffi5Spq%2Fimage.png?alt=media\&token=86d96437-d724-4d55-a2fe-bbf90943eccf)

notice the not found case => return -1

time: O(m\*n), O(8 \*4)

space: O(m\*n), O(8 \*4)

```java
class Solution {
    public int minMutation(String start, String end, String[] bank) {
        // like wordladder
        // use BFS to find sortest path
        // store bank in hashset for checking doest it exist in bank[]
        if (bank == null || bank.length == 0) return -1;
        
        Set<String> set = new HashSet<>();
        for (String s : bank) {
            set.add(s);
        }
        set.remove(start);
        
        Queue<String> queue = new LinkedList<>();
        queue.offer(start);
        int res = 0;
        
        char mutation[] = new char[]{'A', 'C', 'G', 'T'};
        
        while (!queue.isEmpty()) {
            int qSize = queue.size();
            for (int q = 0; q < qSize; q++) {
                String cur = queue.poll();
                
                if (cur.equals(end)) return res;
                
                for (int i = 0; i < cur.length(); i++) {
                    for (int j = 0; j < mutation.length; j++) {
                        char charArray[] = cur.toCharArray();
                        charArray[i] = mutation[j];
                        String newGene = String.valueOf(charArray);
                        if (set.contains(newGene)) {
                            queue.offer(newGene);
                            set.remove(newGene);
                        }
                    }
                }
            }
            res++;
        }
        return -1;
    }
}
```