A Python Recursive Solution by my own:)


  • 0
    I

    Well, it certainly can be done by using three vars to validate four parts in an IP address,but backtracking is subtle.
    var t is the number of IP address, from left to right, counting 4,3,2,1.

    class Solution(object):
        def restoreIpAddresses(self, s, t=4):
            # backtracking solution
            # recursive solution
    
            n = len(s)
            if n <t:
                return []
            d = 3*t-n
            start = 1 if 3-d < 1 else 3-d
            res = []
    
            if t == 1:
                return [s] if 0<=int(s)<=255 and (s[0] != '0' or len(s) == 1) else []
    
            for i in range(start, 4):
                res1 = self.restoreIpAddresses(s[i:], t-1)
    
                for x in res1:
                    tmp = s[:i]
                    if 0<=int(tmp)<=255 and (tmp[0] != '0' or len(tmp) == 1):
                        res.append(tmp+'.'+x)
                    else:
                        return res
    
    
            return res
    

Log in to reply
 

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