433. Minimum Genetic Mutation

[zeikar]

Problem link

https://leetcode.com/problems/minimum-genetic-mutation/

Problem Summary

ACGT로만 이루어진 gene이 둘 주어질 때 startGene 에서 endGene으로 mutate가 가능하면 최소 횟수를 출력하는 문제. mutate는 bank에 있는 문자열로만 가능하다.

Solution

bank 개수 제한이 아주 여유로워서 DFS, BFS 다 가능하다.
일단 간단하게 DFS 백트래킹으로 구현했다. bank로 mutate가 가능한지 판단해서 이동하는 방식.

최단 개수이므로 BFS가 정석이긴 하다.

Source Code

class Solution:
    def minMutation(self, startGene: str, endGene: str, bank: List[str]) -> int:        
        visited = defaultdict(bool)

        # 한글자만 다른지 체크
        def canMutate(gene, newGene):
            diff = 0
            for i in range(len(gene)):
                if gene[i] != newGene[i]:
                    diff += 1
            return diff == 1

        def solve(gene):
            if gene == endGene:
                return 0
            
            ret = float('inf')
            for b in bank:
                if visited[b]:
                    continue

                if canMutate(gene, b):
                    visited[b] = True
                    ret = min(ret, solve(b) + 1)
                    visited[b] = False
                        
            return ret

        result = solve(startGene)
        if result == float('inf'):
            return -1
        return result