Python solution using Bi-directional bfs.


  • 0
    M

    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 https://leetcode.com/problems/word-ladder-ii/. 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
                    visited.add(pattern)
                    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:
                                s_tmp.add(newpattern)
                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.