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)returnfalse;if(s.length>1&& s[0]==='0')returnfalse;if(s >255)returnfalse;returntrue;}function breakString(s, parts){if(parts ===1&&!isValid(s))return[];elseif(parts ===1)return[s];
let ret =[];//break into 3 piecesfor(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);};
/**
* @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
Given an integer array nums that may contain duplicates, return all possible subsets (the power set). The solution set must not contain duplicate subsets....
[Problem Link] Solution here is to add some `ordering` on the resources (i.e. forks) requested by the processes (i.e. the philosophers). Identify the resource...