433.Minimum_Genetic_Mutation(Medium).md

433. Minimum Genetic Mutation (Medium)

Date and Time: Aug 11, 2024, 0:38 (EST)

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

Question:

A gene string can be represented by an 8-character long string, with choices from 'A', 'C', 'G', and 'T'.

Suppose we need to investigate a mutation from a gene string startGene to a gene string endGene where one mutation is defined as one single character changed in the gene string.

• For example, "AACCGGTT" --> "AACCGGTA" is one mutation.

There is also a gene bank bank that records all the valid gene mutations. A gene must be in bank to make it a valid gene string.

Given the two gene strings startGene and endGene and the gene bank bank, return _the minimum number of mutations needed to mutate from startGene to endGene_. If there is no such a mutation, return -1.

Note that the starting point is assumed to be valid, so it might not be included in the bank.

Example 1:

Input: startGene = "AACCGGTT", endGene = "AACCGGTA", bank = ["AACCGGTA"]

Output: 1

Example 2:

Input: startGene = "AACCGGTT", endGene = "AAACGGTA", bank = ["AACCGGTA","AACCGCTA","AAACGGTA"]

Output: 2

Constraints:

• 0 <= bank.length <= 10

• startGene.length == endGene.length == bank[i].length == 8

• startGene, endGene, and bank[i] consist of only the characters ['A', 'C', 'G', 'T'].

Walk-through:

This question is similar to previous question 127. Word Ladder, where we store each pattern for each word in wordList, but in this problem, we try different combination of ['A', 'C', 'T', 'G'] for each index of gene and search if the new combination is in bank, then we can append it to deque[] for next interation.

Python Solution:

class Solution:
    def minMutation(self, startGene: str, endGene: str, bank: List[str]) -> int:
        adj = collections.defaultdict(list)
        for gene in bank:
            for i in range(len(gene)):
                pattern = gene[:i] + "*" + gene[i+1:]
                adj[pattern].append(gene)
        
        deque, visited = collections.deque([startGene]), set()
        visited.add(startGene)
        res = 0
        while deque:
            for _ in range(len(deque)):
                gene = deque.popleft()
                if gene == endGene:
                    return res
                for i in range(len(gene)):
                    pattern = gene[:i] + "*" + gene[i+1:]
                    for nei in adj[pattern]:
                        if nei not in visited:
                            visited.add(nei)
                            deque.append(nei)
            res += 1
        return -1

Time Complexity: $O(n^2 * m)$
Space Complexity: $O(n * m)$, where n is the total number of gene in bank, m is the length of each gene.

Python Optimized Solution:

class Solution:
    def minMutation(self, startGene: str, endGene: str, bank: List[str]) -> int:
        res = 0
        choices = ['A', 'C', 'G', 'T']
        deque = collections.deque([startGene])
        visited = set(startGene)
        while deque:
            for _ in range(len(deque)):
                gene = deque.popleft()
                if gene == endGene:
                    return res
                for i in range(8):
                    for choice in choices:
                        newGene = gene[:i] + choice + gene[i+1:]
                        if newGene in bank and newGene not in visited:
                            deque.append(newGene)
                            visited.add(newGene)
            res += 1
        return -1

Time Complexity: $O(n * m)$
Space Complexity: $O(n * m)$, where n is the total number of gene in bank, m is the length of each gene.