Python easy BFS


  • 0
    J
    import collections
    class Solution(object):
        def minMutation(self, start, end, bank):
            """
            :type start: str
            :type end: str
            :type bank: List[str]
            :rtype: int
            """
            visited = set()
            bank_set = set(bank)
            queue = collections.deque()
            visited.add(start)
            queue.append(start)
            cnt = -1
            while queue:
                cnt += 1
                size = len(queue)
                for _ in range(size):
                    current = queue.popleft()
                    if current == end:
                        return cnt
                    for gene in self.possible_mutation(current, bank):
                        if gene not in visited:
                            visited.add(gene)
                            queue.append(gene)
    
            return -1
        
        def possible_mutation(self, current, bank):
            poss_mut = []
            for gene in bank:
                diff = 0
                for i in range(8):
                    if current[i] != gene[i]:
                        diff += 1
                        if diff > 1:
                            break
                if diff == 1:
                    poss_mut.append(gene)
                    
            return poss_mut
            
    

  • 0
    W

    @Jason1016 Similar to yours, but instead of adding to an visited set, I remove from a not_visited set and use this not_visited set in the possible_mutation function.

    from collections import deque
    
    class Solution(object):        
        def minMutation(self, start, end, bank):
            """
            :type start: str
            :type end: str
            :type bank: List[str]
            :rtype: int
            """        
            not_visited = set(bank)
            
            def mutations_generator(gene):
                for mutation in list(not_visited):
                    diff = 0
                    for i in range(0, len(gene)):
                        if diff > 1:
                            continue
                        elif gene[i] != mutation[i]:
                            diff += 1
                    if diff == 1:
                        not_visited.remove(mutation)
                        yield mutation
                        
    
            open_nodes = deque()
            
            open_nodes.append((start, 0))
            
            while len(open_nodes) > 0:
                gene_tuple = open_nodes.pop()
                
                if gene_tuple[0] == end:
                    return gene_tuple[1]
                
                next_mutation_count = gene_tuple[1] + 1
                
                for mutation in mutations_generator(gene_tuple[0]):
                    open_nodes.append((mutation, next_mutation_count))
            
            return -1
    

Log in to reply
 

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