433. Minimum Genetic Mutation

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

Explanation

유전자 문자열은 A, C, G, T로 이루어진 길이 8의 문자열이다. start문자열은 유전자 문자열이고, end문자열은 돌연변이 문자열이다. (돌연변이 문자열이 아닐 수도 있다) start배열에서 단일 문자를 변경하여 돌연변이 문자열(end)이 될 수 있는 유효한 문자열은 bank배열에 저장되어 있다. 다시 말해서, bank배열에 저장되어 있는 문자로만 변경하면서 end배열이 되어야 한다.

start문자열에서 단일 문자를 최소 개수만큼 사용하여 end문자열로 바꿨을 때의 가장 적은 방법의 수를 반환하라.

문제를 이해하려고 두번, 세번 읽었다. 처음에는 start배열을 뒤에서부터 접근하여 end배열의 문자와 다르면 리스트 슬라이싱을 활용해 끼워맞추는 방법을 사용하였지만 틀렸다.

이 방법은 bfs를 활용한 방법이다. 조금만 더 머리를 썼다라면, 떠올랐을 수도 있는데 문자열을 bfs를 사용하여 문제를 푼 경험이 없어서 떠오르지가 않았다.

Algorithm

BFS

queue에 start문자열과 0(=최소 방법의 수)을 넣는다. start문자열의 각 문자를 ATGC를 한번씩 사용해서 변경한 후 bank배열에 존재하는 지 확인한다. 존재한다면, bank배열에 존재하는 문자열을 제거 후 카운트를 누적시키고 다시 queue에 바뀐 문자열을 넣고 while반복문을 돌면서 start문자열과 end가 같은 문자열일 때 까지 돈다.

class Solution:
    def minMutation(self, start: str, end: str, bank: List[str]) -> int:
        # [1] initialize queue with starting gene
        q, bank = collections.deque([(start,0)]), set(bank)

        while q:
            g, m = q.popleft()
            if g == end : return m
            
            # [2] try all possible mutations, namely,
            #     try every nucleotide in each position
            for i in range(len(g)):
                for n in "ATGC":
                    gm = g[0:i] + n + g[i+1:]
                    # [3] successful branches are added to
                    #     the queue for further mutagenesis
                    if gm in bank:
                        bank.remove(gm)
                        q.append((gm, m+1))
        
        return -1

Time Complexity

문자열이 만들어질 때 마다 모든 경우의 수를 체크하니까 O(N^2)이 아닐까 싶다.