LeetCode 433 - Minimum Genetic Mutation

Minimum Genetic Mutation - LeetCode

 

‘A’, ‘C’, ‘G’, ‘T’로 이루어진 8글자 문자열

startGene에서 endGene으로 변형하는데 필요한 최소 변경 횟수를 찾으시오. 없다면 -1

한 번에 하나의 문자만 변경이 가능하며 변경된 유전자 문자열은 bank에 반드시 존재해야 한다.

startGene에서부터 탐색을 시작해서 첫 글자부터 ‘A’, ‘C’, ‘G’, ‘T’로 바꿔가면서 탐색을 진행한다.

최소 횟수를 구하고 있기 때문에 BFS를 통해 처리하겠다.

현재 상태에서 위치의 문자를 변경해 가며 bank에 존재한다는 조건에 맞다면 q에 집어넣는다.

class Solution {

    static final char[] GENES = {'A', 'C', 'G', 'T'};

    static class Mutate {
        String gene;
        int count;

        public Mutate(String gene, int count) {
            this.gene = gene;
            this.count = count;
        }
    }

    public int minMutation(String startGene, String endGene, String[] bank) {
        Set<String> bankSet = Arrays.stream(bank).collect(Collectors.toSet());
        Set<String> visited = new HashSet<>();
        if (!bankSet.contains(endGene)) return -1;
        Queue<Mutate> q = new LinkedList<>();
        q.add(new Mutate(startGene, 0));
        visited.add(startGene);

        while (!q.isEmpty()) {
            Mutate curr = q.poll();
            if (curr.gene.equals(endGene)) {
                return curr.count;
            }
            StringBuilder sb = new StringBuilder(curr.gene);
            for (int i = 0 ; i < 8; i++) {
                for (char c : GENES) {
                    StringBuilder next = new StringBuilder(sb);
                    if (next.charAt(i) != c) {
                        next.setCharAt(i, c);
                        if (visited.contains(next.toString())) continue;
                        if (bankSet.contains(next.toString())) {
                            q.add(new Mutate(next.toString(), curr.count + 1));
                            visited.add(next.toString());
                        }
                    }
                }
            }
        }

        return -1;
    }
}