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
ремонт смартфонов в москве рядом
Your insights are refreshing! I can’t wait to dive into the Refurbished Electronic Bazzar.
חוויית אירוח בלתי נשכחת. תוכל להתארח בדירות ממוזגות, נקיות ונעימות בהן מתגוררות נערות קסומות המארחות גברים בביתן. אם בא לך צריך עכשיו! דירות דיסקרטיות לבילוי אינטימי אולי אתה לא מודע לזה, אבל דירות דיסקרטיות הן בדיוק מה שלבך מחפש ומה שגופך visit site