Easy Recursive Python Solution ( With Comments ) 32ms


  • 0
    D

    class Solution(object):

    def getDiff(self,x,y):
        count = 0
        for a,b in zip(x,y):
            if a!=b:
                count+=1
        
        return count
    
    def isDiffOne(self,x,y):
        return self.getDiff(x,y)==1
    
    
    def lowerDiff(self,end,bank):
        
        minimum = len(end)
        min_gene = None
        for gene in bank:
            
            if gene==end:
                return gene
            
            diff = self.getDiff(gene,end)
            if diff<=minimum:
                min_gene = gene
                minimum = diff
        
        return min_gene
        
    def minMutation(self, start, end, bank):
        """
        :type start: str
        :type end: str
        :type bank: List[str]
        :rtype: int
        """
        
        print(start)
        
        if start==end:
            return 0
        
        if end not in bank:
            return -1
        
        if start in bank:
            bank.remove(start)
        
        gb = []
        
        #Get 1 distance genes
        for gene in bank:
            
            if(self.isDiffOne(start,gene)):
                gb.append(gene)
        
        # If gb is empty, that means there are no more possible alternatives.
        if len(gb)==0:
            return -1
        
        #Get closest gene to end. When we have multiple possible combinations, get the gene which is closest to end
        new_start = self.lowerDiff(end,gb)
        
        p = self.minMutation(new_start,end,bank)
        
        # If any function returns -1, that means that there is no possible path from start to end.
        if p<0:
            return -1
        else:
            return 1+p

Log in to reply
 

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