Accepted python solution with dfs


  • 0
    S
    def restoreIpAddresses(self, s):
        """
        :type s: str
        :rtype: List[str]
        """
        if len(s) == 4:
            return [ s[0]+'.'+s[1] + '.' + s[2] + '.' + s[3]]
        solution = ''
        result = []
        pos = 4 # how many blocks are remaining
        nxtlen = 0 #the next piece length
        self.myIP(s, solution, result, pos, nxtlen)
        return result
        
    def myIP(self, s, solution, result, pos, nxtlen):
        if  len(s)==0 or (pos == 1 and ( len(s) >3 or int(s)>255) ) or (pos== 1 and  len(s)>1 and s[0]=='0') or (pos>1 and len(s)==1):
            return
        if len(s) == 1 or len(s) > 1 and s[0]!= '0' and pos == 1 and len(s)>=1 and len(s) <=3 and int(s)<=255:
            solution += '.' + s
            sol = copy.copy(solution)
            result.append(sol)
            return
        for i in range(0,3):
            newitem = s[0:i+1]
            if len(newitem) == 1 or len(newitem) > 1 and newitem[0]!= '0' and len(s[i+1:]) <= (pos-1)*3 and  int(newitem) <= 255:
                if pos == 4:
                    solution += newitem
                    nxtlen = len(newitem)
                else:
                    solution += '.'+ s[0:i+1]
                    nxtlen = len(newitem)+1
                pos -= 1
                self.myIP(s[i+1:],solution, result, pos, nxtlen)
                solution = solution[0:len(solution)-nxtlen]
                pos += 1
    

    I dealt with a lot of corner cases in the second method, where it needs improvement.


Log in to reply
 

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