题目

给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。

示例:

输入: "25525511135"
输出: ["255.255.11.135", "255.255.111.35"]

" class=“notranslate”>

给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。

示例:

输入: "25525511135"
输出: ["255.255.11.135", "255.255.111.35"]

思路

搜索吧
根据边界情况和待搜索的母串决定是停止搜索还是继续搜索

注意的是 num = 0的时候，只搜索一遍。

代码

class Solution {
public:
    void _restoreIpAddresses(vector<string> &ans, string &s, string tmp, int cnt, int l) {
        if (cnt == 4) {
            if (l >= s.size()) ans.push_back(tmp.substr(1,tmp.size() - 1));
            return;
        } 
        int num = 0, i = 0;
        while ((num = num * 10 + s[l + i] - '0') <= 255 && l + i < s.size()) {
            _restoreIpAddresses(ans, s, tmp + "." + to_string(num), cnt + 1, l + i + 1);
            ++i;
            if (num == 0) break;
        }
        return ;
    }
    vector<string> restoreIpAddresses(string s) {
        vector<string>ans;
        _restoreIpAddresses(ans, s, "", 0, 0);
        return ans;
    }
};
执行用时 : 4 ms, 在所有 C++ 提交中击败了 93.35% 的用户

总结

1.to_string 可以将ｉｎｔ转为string
2.substr 的效率蛮不错的，没啥影响好像。