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"]

Problem Link

This was an interesting problem. We divide the string into fragments (starting with 4) and return strings at each recursion.

Gotcha 1: for some reason i thought for the final fragment (e.g ‘123’) would return ([‘1’, ‘2’, ‘3’]). if we’re at the last fragment we simply return the string (if its valid).

Gotcha 2: an ip fragment cannot be more than 255 (and it cannot be more than 3 numbers, but if we check if fragment is less than 255, the max char check takes care of itself)

Gotcha 3: Just ‘0’ as a fragment is valid but ‘0xx’ (e.g. ’01’, ‘001’, ‘010’ etc) are not. We need to check for that.

Gotcha 4: an empty ” fragment is invalid! Make sure we check for that and return an empty array.

/**
 * @param {string} s
 * @return {string[]}
 */
 
function isValid(s) {
  if (s.length === 0) return false;
  if (s.length > 1 && s[0] === '0') return false;
  if (s > 255) return false;
  return true;
}
 
function breakString(s, parts) {
  if (parts === 1 && !isValid(s)) return [];
  else if (parts === 1) return [s];
 
  let ret = [];
 
  //break into 3 pieces
  for (let i = 1 ; i <= 3 ; i++ ) {
    let part1 = s.slice(0, i);
    let part2 = s.slice(i);
    if (!isValid(part1)) continue;
    let tmp = breakString(part2, parts-1);
    if (tmp.length === 0 ) continue;
    tmp = tmp.map((str) => part1 + "." + str);
    ret = ret.concat(tmp);      
  }
 
  return ret;
 
}
 
var restoreIpAddresses = function(s) {
    return breakString(s, 4);
};

Time complexity?
https://cs.stackexchange.com/questions/121293/time-complexity-for-the-restore-ip-addresses-problem