{"id":2186,"date":"2016-09-11T11:25:56","date_gmt":"2016-09-11T03:25:56","guid":{"rendered":"http:\/\/boweihe.me\/?p=2186"},"modified":"2016-09-11T11:25:56","modified_gmt":"2016-09-11T03:25:56","slug":"leetcode-93-restore-ip-addresses","status":"publish","type":"post","link":"https:\/\/dayandcarrot.space\/?p=2186","title":{"rendered":"LeetCode 93. Restore IP Addresses"},"content":{"rendered":"

\u601d\u8def<\/h3>\n

\u56de\u6eaf(backtracing)\uff0c\u7528s\u7684\u8d77\u59cb\u4f4d\u7f6epos\u8868\u793a\u5f53\u524d\u7684\u72b6\u6001\uff08pos\u4e4b\u524d\u7684\u5df2\u7ecf\u5904\u7406\u5b8c\uff09\u3002\u90a3\u4e48\u5c31\u4f9d\u6b21\u5c1d\u8bd51~3\u4f4d\u7684\u5b57\u7b26\u770b\u770b\u662f\u5426\u7b26\u5408\u8981\u6c42\uff0c\u7b26\u5408\u5c31\u628a\u7ed3\u679c\u66f4\u65b0\u5230buffer\u91cc\uff0c\u672a\u5b8c\u6210\u5c31\u9012\u5f52\u7ee7\u7eed\uff0c\u7136\u540e\u9012\u5f52\u8fd4\u56de\u7684\u65f6\u5019\u8bb0\u5f97\u628abuffer\u6062\u590d\u5230\u4e4b\u524d\u7684\u72b6\u6001\u3002
\n\u6309\u7167\u9898\u76ee\u7684\u610f\u601d\uff0c\u5e94\u8be5\u4e0d\u5141\u8bb8IP\u5730\u5740\u6709\u524d\u5bfc0\uff0c\u537301.01.01.01\u8fd9\u79cd\u72b6\u6001.
\n\u5bf9\u4e86\uff0cstoi\u51fd\u6570\u5f88\u597d\u7528\uff0c\u5e94\u8be5\u662fC++11\u65b0\u52a0\u7684\u3002<\/p>\n

\u4ee3\u7801<\/h3>\n
class Solution {\npublic:\n    bool isValidSubAddr(const string& s, int pos, int len){\n        if(pos + len > s.size())\n            return false;\n        int val = stoi(s.substr(pos, len));\n        if(val >= 0 && val <= 255){\n            if(val < 10 && len > 1)\n                return false;\n            else if(val < 100 && len > 2)\n                return false;\n            return true;\n        }\n        return false;\n    }\n    void restoreSub(vector<string>& results, const string& s, int pos, int remainingDot, string& buffer){\n        if(remainingDot == 0 || pos >= s.size())\n            return;\n        int buffSize = buffer.size();\n        for(int len=1; len<=3; len++){\n            if(!isValidSubAddr(s, pos, len))\n                continue;\n            buffer += s.substr(pos, len);\n            if(pos + len == s.size()){\n                \/\/one solution\n                if(remainingDot == 1) \/\/otherwise, the split cannot be finished\n                    results.push_back(buffer);\n            } else {\n                buffer += \".\";\n                \/\/continue try\n                restoreSub(results, s, pos+len, remainingDot-1, buffer);\n            }\n            buffer.erase(buffSize); \/\/restore state\n        }\n    }\n    vector<string> restoreIpAddresses(string s) {\n        vector<string> results;\n        if(s.empty()){\n            return results;\n        }\n        string buffer;\n        restoreSub(results, s, 0, 4, buffer);\n        return results;\n    }\n};<\/pre>\n
 <\/p>\n","protected":false},"excerpt":{"rendered":"
\u601d\u8def \u56de\u6eaf(backtracing)\uff0c\u7528s\u7684\u8d77\u59cb\u4f4d\u7f6epos\u8868\u793a\u5f53\u524d\u7684\u72b6\u6001\uff08pos\u4e4b\u524d\u7684\u5df2\u7ecf\u5904\u7406\u5b8c\uff09\u3002\u90a3\u4e48\u5c31\u4f9d\u6b21\u5c1d\u8bd51~3\u4f4d\u7684\u5b57\u7b26\u770b\u770b\u662f\u5426\u7b26\u5408\u8981\u6c42\uff0c\u7b26\u5408\u5c31\u628a\u7ed3\u679c\u66f4\u65b0\u5230buffer\u91cc\uff0c\u672a\u5b8c\u6210\u5c31\u9012\u5f52\u7ee7\u7eed\uff0c\u7136\u540e\u9012\u5f52\u8fd4\u56de\u7684\u65f6\u5019\u8bb0\u5f97\u628abuffer\u6062\u590d\u5230\u4e4b\u524d\u7684\u72b6\u6001\u3002 \u6309\u7167\u9898\u76ee\u7684\u610f\u601d\uff0c\u5e94\u8be5\u4e0d\u5141\u8bb8IP\u5730\u5740\u6709\u524d\u5bfc0\uff0c\u537301.01.01.01\u8fd9\u79cd\u72b6\u6001. \u5bf9\u4e86\uff0cstoi\u51fd\u6570\u5f88\u597d\u7528\uff0c\u5e94\u8be5\u662fC++11\u65b0\u52a0\u7684\u3002 \u4ee3\u7801 class Solution { public: bool isValidSubAddr(const string& s, int pos, int len){ if(pos + len > s.size()) return false; int val = stoi(s.substr(pos, len)); if(val >= 0 && val <= 255){ if(val < 10 && len > 1) return false; else if(val < 100 && len > 2) return false; […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4],"tags":[66,151],"class_list":["post-2186","post","type-post","status-publish","format-standard","hentry","category-study","tag-leetcode-oj","tag-151"],"_links":{"self":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts\/2186","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=2186"}],"version-history":[{"count":0,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts\/2186\/revisions"}],"wp:attachment":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=2186"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=2186"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=2186"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}