clean python BFS solution, very similar to word ladder problem


  • 0
    I
    from collections import deque
    class Solution(object):
        def one_mutation_genes(self, gene):
            result = []
            nucleotides = ['A', 'C', 'T', 'G']
            for idx, char in enumerate(gene):
                for letter in nucleotides:
                    if char != letter:
                        result.append(gene[:idx] + letter + gene[idx+1:])
                
            return result
            
        def minMutation(self, start, end, bank):
            """
            :type start: str
            :type end: str
            :type bank: List[str]
            :rtype: int
            """
            if not bank or not start or not end:
                return -1
                
            queue = deque([start])
            bank_set = set(bank)
            min_dist = 0
            
            while queue:
                queue_size = len(queue)
                for i in xrange(queue_size):
                    curr_gene = queue.pop()
                    if curr_gene == end:
                        return min_dist
                    
                    for adj_gene in self.one_mutation_genes(curr_gene):
                        if adj_gene not in bank_set:
                            continue
                        
                        bank_set.remove(adj_gene)
                        queue.appendleft(adj_gene)
                            
                min_dist += 1
                    
            return -1

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.