Skip to content

93. Restore IP Addresses

https://leetcode.com/problems/restore-ip-addresses/

js
/**
 * @param {string} s
 * @return {string[]}
 */
var restoreIpAddresses = function(s) {
  var result = []
  buildIp(s, [], result)
  return result
}

function buildIp(s, nums, result) {
  if (nums.length === 4) {
    if (!s) {
      result.push(nums.join('.'))
    }
    return
  }

  for (let i = 0; i < 3; i++) {
    if (i >= s.length) {
      return
    }

    if (i > 0 && s[0] === '0') {
      return
    }

    let num = +s.substring(0, i + 1)
    if (num <= 255) {
      buildIp(s.substring(i + 1), nums.concat([num]), result)
    }
  }
}
py
class Solution(object):

    def restoreIpAddresses(self, s):
        """
        :type s: str
        :rtype: List[str]
        """
        result = []
        self.buildIp(s, [], result)
        return result

    def buildIp(self, s, nums, result):
        if len(nums) == 4:
            if not s:
                result.append('.'.join(nums))
            return

        for i in range(3):
            if i >= len(s):
                return
            if i > 0 and s[0] == '0':
                return
            if int(s[:i + 1]) <= 255:
                self.buildIp(s[i + 1:], nums + [s[:i + 1]], result)