18 lines of Python code, BFS


  • 0
    J

    Improvement based on jianxian2's solution.

    # BFS
    class Solution():
        def minMutation(self, start, end, bank):
                """
                :type start: str
                :type end: str
                :type bank: List[str]
                :rtype: int
                """
                queue =[(start,[start])]
                while queue:
                    vertex,path=queue.pop(0) # breadth first search
                    # print path
                    pool=bank[:] # a copy of current bank
                    for item in pool:
                        if self.differBySingleChar(item,vertex):
                            if item == end:
                                return len(path)
                            else:
                                queue.append((item,path+[item]))
                                bank.remove(item)  # remove used item
                return -1
    
        def differBySingleChar(self,str1,str2): # Judge if one gene can be reached by another by one mutation
                count = 0
                for i in range(len(str1)):
                    if str1[i] != str2[i]:
                        count += 1
                return count == 1
    

Log in to reply
 

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