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