Easy Recursive Python Solution ( With Comments ) 32ms

  • 0

    class Solution(object):

    def getDiff(self,x,y):
        count = 0
        for a,b in zip(x,y):
            if a!=b:
        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
        if start==end:
            return 0
        if end not in bank:
            return -1
        if start in bank:
        gb = []
        #Get 1 distance genes
        for gene in bank:
        # 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
            return 1+p

Log in to reply

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