433. Minimum Genetic Mutation

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

Medium

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 start to a gene string end 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 start and end and the gene bank bank, return the minimum number of mutations needed to mutate from start to end. 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: start = "AACCGGTT", end = "AACCGGTA", bank = ["AACCGGTA"]
Output: 1

Example 2:

Input: start = "AACCGGTT", end = "AAACGGTA", bank = ["AACCGGTA","AACCGCTA","AAACGGTA"]
Output: 2

Example 3:

Input: start = "AAAAACCC", end = "AACCCCCC", bank = ["AAAACCCC","AAACCCCC","AACCCCCC"]
Output: 3

Constraints:

start.length == 8
end.length == 8
0 <= bank.length <= 10
bank[i].length == 8
start, end, and bank[i] consist of only the characters ['A', 'C', 'G', 'T'].

Problem

Each string represents a gene sequence. During mutation, only one character changes at a time. Both intermediate and final states must exist in the gene bank. Return the number of mutations needed, or -1 if impossible.

Approach

Starting from start, use BFS to find genes in the bank that differ by exactly one character. Push valid mutations into a queue and check if we’ve reached end.

Write a contains method to check if a gene is in the bank.
Write a canMutate method to verify exactly one character differs.
Declare a queue and visited map.
Traverse the queue level by level, counting mutations.
If we reach end, return the count. If the queue is exhausted, return -1.

Source Code

func minMutation(start string, end string, bank []string) int {
    queue := []string{}
    visited := make(map[string]bool, 0)

    if contains(bank, end) && start == end {
        return -1
    }

    queue = append(queue, start)
    visited[start] = true
    ans := 0
    for len(queue) != 0 {
        length := len(queue)
        for i := 0; i < length; i++ {
            current := queue[0]
            queue = queue[1:]

            if current == end {
                return ans
            }

            for _, b := range bank {
                if canMutate(b, current) && !visited[b] {
                    queue = append(queue, b)
                    visited[b] = true
                }
            }
        }
        ans++
    }
    return -1
}

func canMutate(str1, str2 string) bool {
    counter := 0
    for i := 0; i < len(str1); i++ {
        if str1[i] != str2[i] {
            counter++
        }
    }
    return counter == 1
}

func contains(bank []string, tofind string) bool {
    for _, b := range bank {
        if tofind == b {
            return true
        }
    }
    return false
}

Closing

Do you have a better or simpler solution?

Feel free to leave a comment on my blog. Your feedback motivates me to keep writing. Thank you for reading, and let’s grow together to become better versions of ourselves.

Alan Zhan Blog