Python solution using BFS


  • 0
    W
    class Solution(object):
        def minMutation(self, start, end, bank):
            """
            :type start: str
            :type end: str
            :type bank: List[str]
            :rtype: int
            """
            queue = collections.deque()
            visited = set()
            queue.append((start, 0))
            dict_words = set(bank)
            while queue:
                word, steps = queue.popleft()
                if word == end:
                    return steps
                if word not in visited:
                    visited.add(word)
                    for i in range(len(word)):
                        for s in ["A", "C", "G", "T"]:
                            if s != word[i]:
                                mutate_word = word[:i] + s + word[i+1:]
                                if mutate_word in dict_words and mutate_word not in visited:
                                    queue.append((mutate_word, steps + 1))
            return -1
    

Log in to reply
 

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