A Python Recursive Solution by my own:)

  • 0

    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):
                        return res
            return res

Log in to reply

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