Problem statement

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

Solution

This problem is basically the same as problem 0126 and 0127 Word Ladder (II), but here we have smaller alphabet. Let n be number of words in our bank, then for each word we have maximum 3 * 8 = 24 neighbors, each of them can be checked in O(8) time. So we need O(mnk^2) = O(8^2 * 3 * n), where m is alphabet size, k is word length time to create adjacency list. Then we use BFS with queue to find the shortest path with O(E) = O(mnk) complexity.

Complexity

Overall complexity is still O(mnk^2) time and O(mkn) space. I think we can use Bit Manipulation for this problem, which can increase speed.

Code

class Solution(object):
    def minMutation(self, start, end, bank):
        queue = deque([(0, start)])
        bankSet = set(bank)
        
        while queue:
            step, curr = queue.popleft()
            if curr == end: return step
            for i in range(8):
                for c in "AGCT":
                    neib = curr[:i] + c + curr[i+1:]
                    if neib in bankSet:
                        bankSet.remove(neib)
                        queue.append((step + 1, neib))
                        
        return -1