93. Restore IP Addresses

Problem

Given a string containing only digits, restore it by returning all possible valid IP address combinations.

Example:

Input: "25525511135"
Output: ["255.255.11.135", "255.255.111.35"]

Solution 1

/**
 * @param {string} s
 * @return {string[]}
 */
var restoreIpAddresses = function(s) {
  var res = [];
  helper(s, 0, [], res);
  return res;
};

var helper = function (s, start, now, res) {
  var str = '';
  var num = 0;

  if (now.length === 4) {
    if (start === s.length) res.push(now.join('.'));
    return;
  }

  for (var i = 1; i <= 3; i++) {
    str = s.substr(start, i);
    if (str.length === 1 || str[0] !== '0') {
      num = Number(str);
      if (0 <= num && num <= 255) {
        now.push(num);
        helper(s, start + i, now, res);
        now.pop();
      }
    }
  }
};

Explain:

nope.

Complexity:

• Time complexity : O(1).
• Space complexity : O(1).

Solution 2

/**
 * @param {string} s
 * @return {string[]}
 */
var restoreIpAddresses = function(s) {
  var res = [];
  var len = s.length;
  var str1 = '';
  var str2 = '';
  var str3 = '';
  var str4 = '';

  for (var i = 1; i <= 3; i++) {
    for (var j = 1; j <= 3; j++) {
      for (var k = 1; k <= 3; k++) {
        for (var m = 1; m <= 3; m++) {
          str1 = s.substr(0, i);
          str2 = s.substr(i, j);
          str3 = s.substr(i + j, k);
          str4 = s.substr(i + j + k, m);
          if (i + j + k + m === len
              && isValid(str1)
              && isValid(str2)
              && isValid(str3)
              && isValid(str4)) {
            res.push(str1 + '.' + str2 + '.' + str3 + '.' + str4);
          }
        }
      }
    }
  }

  return res;
};

var isValid = function (str) {
  if (str.length > 1 && str[0] === '0') return false;
  if (Number(str) > 255) return false;
  return true;
};

Explain:

nope.

Complexity:

• Time complexity : O(1).
• Space complexity : O(1).