Restore IP Addresses

Problem: Restore IP Addresses

We just do backtracking on the string to get results.

Note that we can return later if the left characters cannot make up to remaining IP domains and 0 beginning non-zero numbers are not allowed.

Code in Python:

class Solution(object):
    def restoreIpAddresses(self, s):
        """
        :type s: str
        :rtype: List[str]
        """
        ans = []
        def restoreIp(pos, segments, ip):
            if segments < 0:
                ans.append(ip[:len(ip)-1])
                return
            for x in xrange(pos, len(s)):
                if len(s)-x-1 > 3*segments:
                    continue
                if len(s)-x-1 < 1*segments:
                    break
                if int(s[pos:x+1]) >= 0 and int(s[pos:x+1]) <= 255:
                    if x+1-pos > 1 and s[pos] == '0':
                        continue
                    restoreIp(x+1, segments-1, ip+s[pos:x+1]+".")
        restoreIp(0, 3, '')
        return ans