{"id":11142,"date":"2020-02-29T07:27:50","date_gmt":"2020-02-29T07:27:50","guid":{"rendered":"http:\/\/www.softwareeverydayblog.com\/?p=11142"},"modified":"2020-03-01T23:59:32","modified_gmt":"2020-03-01T23:59:32","slug":"programming-problem-restore-ip-addresses","status":"publish","type":"post","link":"https:\/\/www.softwareeverydayblog.com\/?p=11142","title":{"rendered":"[Programming Problem] Restore IP Addresses"},"content":{"rendered":"<p>Given a string containing only digits, restore it by returning all possible valid IP address combinations.<\/p>\n<pre lang=\"text\">\r\nExample:\r\n\r\nInput: \"25525511135\"\r\nOutput: [\"255.255.11.135\", \"255.255.111.35\"]\r\n<\/pre>\n<p><a href=\"https:\/\/leetcode.com\/problems\/restore-ip-addresses\/\" rel=\"noopener noreferrer\" target=\"_blank\">Problem Link<\/a><\/p>\n<p>This was an interesting problem. We divide the string into fragments (starting with 4) and return strings at each recursion.<\/p>\n<p><strong>Gotcha 1<\/strong>: for some reason i thought for the final fragment (e.g &#8216;123&#8217;) would return ([&#8216;1&#8217;, &#8216;2&#8217;, &#8216;3&#8217;]). if we&#8217;re at the last fragment we simply return the string (if its valid).<\/p>\n<p><strong>Gotcha 2<\/strong>: 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)<\/p>\n<p><strong>Gotcha 3<\/strong>: Just &#8216;0&#8217; as a fragment is valid but &#8216;0xx&#8217; (e.g. &#8217;01&#8217;, &#8216;001&#8217;, &#8216;010&#8217; etc) are not. We need to check for that.<\/p>\n<p><strong>Gotcha 4<\/strong>: an empty &#8221; fragment is invalid! Make sure we check for that and return an empty array. <\/p>\n<pre lang=\"javascript\">\r\n\/**\r\n * @param {string} s\r\n * @return {string[]}\r\n *\/\r\n\r\nfunction isValid(s) {\r\n  if (s.length === 0) return false;\r\n  if (s.length > 1 && s[0] === '0') return false;\r\n  if (s > 255) return false;\r\n  return true;\r\n}\r\n\r\nfunction breakString(s, parts) {\r\n  if (parts === 1 && !isValid(s)) return [];\r\n  else if (parts === 1) return [s];\r\n  \r\n  let ret = [];\r\n  \r\n  \/\/break into 3 pieces\r\n  for (let i = 1 ; i <= 3 ; i++ ) {\r\n    let part1 = s.slice(0, i);\r\n    let part2 = s.slice(i);\r\n    if (!isValid(part1)) continue;\r\n    let tmp = breakString(part2, parts-1);\r\n    if (tmp.length === 0 ) continue;\r\n    tmp = tmp.map((str) => part1 + \".\" + str);\r\n    ret = ret.concat(tmp);      \r\n  }\r\n    \r\n  return ret;\r\n\r\n}\r\n\r\nvar restoreIpAddresses = function(s) {\r\n    return breakString(s, 4);\r\n};\r\n<\/pre>\n<p><strong>Time complexity?<\/strong><br \/>\nhttps:\/\/cs.stackexchange.com\/questions\/121293\/time-complexity-for-the-restore-ip-addresses-problem<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Given a string containing only digits, restore it by returning all possible valid IP address combinations. Example: Input: &#8220;25525511135&#8221; Output: [&#8220;255.255.11.135&#8221;, &#8220;255.255.111.35&#8221;] 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 [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-11142","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"_links":{"self":[{"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=\/wp\/v2\/posts\/11142","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=11142"}],"version-history":[{"count":5,"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=\/wp\/v2\/posts\/11142\/revisions"}],"predecessor-version":[{"id":11148,"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=\/wp\/v2\/posts\/11142\/revisions\/11148"}],"wp:attachment":[{"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=11142"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=11142"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=11142"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}