python BFS


  • 0
    E

    Do a BFS. In python it's not possible to mutate a string, so use tuples.

    class Solution(object):
        def openLock(self, deadends, target):
            """
            :type deadends: List[str]
            :type target: str
            :rtype: int
            """
            def tup(s):
                return tuple(map(int,s))
            
            initial=tup("0000")
            target=tup(target)
            deadends=set(map(tup,deadends))
            front,newfront=[initial],[]
            seen={initial}
            steps=0
            
            while front:
                while front:
                    s = front.pop()
                    if s in deadends: continue
                    elif s == target: return steps
                    for i in xrange(4):
                        for d in (-1,1):
                            old = s[i]
                            si = (10+old+d)%10
                            ss = tuple(s[:i]+(si,)+s[i+1:])
                            if ss not in seen:
                                newfront.append(ss)
                                seen.add(ss)
                newfront,front=front,newfront
                steps+=1
            return -1
    

  • 0
    E

    Alternatively, use strings

    class Solution(object):
        def openLock(self, deadends, target):
            """
            :type deadends: List[str]
            :type target: str
            :rtype: int
            """
            initial="0000"
            deadends = set(deadends)
            front,newfront=[initial],[]
            seen={initial}
            steps=0
            
            zero = ord("0")
            while front:
                while front:
                    s = front.pop()
                    if s in deadends: continue
                    elif s == target: return steps
                    for i in xrange(4):
                        for d in (-1,1):
                            old = ord(s[i])-zero
                            si = (10+old+d)%10
                            ss = s[:i]+chr(si+zero)+s[i+1:]
                            if ss not in seen:
                                newfront.append(ss)
                                seen.add(ss)
                newfront,front=front,newfront
                steps+=1
            return -1
    

Log in to reply
 

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