Short Python DFS/BFS beats 98%


  • 0

    Very straight forward one. For DFS version, we can using memo to speed it up when test cases get bigger.

    class Solution(object):
        def minMutation(self, start, end, bank):
            """
            :type start: str
            :type end: str
            :type bank: List[str]
            :rtype: int
            """
            def dfs(curr, step, seen):
                if curr == end:
                    self.ans = min(self.ans, step)
                else:
                    for NEXT in dic[curr] - seen:
                        dfs(NEXT, step+1 , seen | {NEXT})
                        
            dic = {a: {b for b in bank if sum(a[i] != b[i] for i in range(8)) == 1} for a in [start] + bank}
            self.ans = float('inf')
            dfs(start, 0, set())
            return (self.ans, -1)[self.ans == float('inf')]
    

    And the BFS version as attached.

    class Solution(object):
        def minMutation(self, start, end, bank):
            """
            :type start: str
            :type end: str
            :type bank: List[str]
            :rtype: int
            """
            dic = {a: {b for b in bank if sum(a[i] != b[i] for i in range(8)) == 1} for a in [start] + bank}
            ans, queue, seen = float('inf'), collections.deque([(start, 0)]), set()
            while queue:
                curr, step = queue.popleft()
                if curr == end: return step
                seen.add(curr)
                queue.extend([(word, step+1) for word in dic[curr] - seen])
            return -1
    

Log in to reply
 

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