BFS search for valid IP in Python


  • 0
    B
    class Solution:
    # @param s, a string
    # @return a list of strings
    def restoreIpAddresses(self, s):
        if not s:
            return []
        
        BFSstack=[]
        BFSstack.append((0,0,[]))
        
        end=len(s)
        
        result=[]
        
        while BFSstack:
            start,count,temp=BFSstack.pop(0)
            if start==end:
                if count==4:
                    result.append(temp[:])
                    continue
                else:
                    continue
            
            if count>4:
                continue
                
            
            for i in range(start+1,end+1):
                if i-start>3:
                    break
                word=s[start:i]
                if int(word)>=0 and int(word)<=255:
                    if not (len(word)>1 and word[0]=='0'):
                        newtemp=temp[:]
                        newtemp.append(word)
                        BFSstack.append((i,count+1,newtemp))
                    
        sresult=[]
            
        for each in result:
            sresult.append(".".join(each))
            
        return sresult
    

    I do feel it used a lot of space (copy of temp), not ideal compared with just DFS backtracking


Log in to reply
 

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