Python solution using Bi-directional bfs.

  • 0

    Here is my solution using Bi-directional bfs. 1-direction solution got timed out so I changed it to 2-ended solution. For practice, another similar problem that uses Bi-directional bfs is Following is my solution:

        def openLock(self, deadends, target):
            visited = set(deadends)
            s1 = set(["0000"])
            s2 = set([target])
            if "0000" in deadends:
                return -1
            cnt = 0
            while s1 and s2:
                s_tmp = set()
                while s1:
                    pattern = s1.pop()
                    if pattern in s2:
                        return cnt
                    for i in range(4):
                        for offset in [1, -1]:
                            newpattern = pattern[:i] + str((int(pattern[i])+offset)%10) + pattern[i+1:]
                            if newpattern not in visited:
                s1 = s_tmp
                s1, s2 = s2, s1
                cnt += 1
            return -1

Log in to reply

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