93.restore-ip-addresses.md

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

示例:

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

---

解题思路

dfs + 剪枝

代码

class Solution {
public:
    vector<string> ans;
    vector<string> restoreIpAddresses(string s) {
        dfs(s, 0, "", 0);
        return ans;
    }
    // i: 当前位置；path:当前结果；p:段数
    void dfs(string &s, int i, string path, int p){
        if (p > 4) return ;
        if (i == s.size()) {
            if (p == 4) ans.push_back(path.substr(1));
            return ;
        }
        int k = 0;
        for (int j = 1; j <= 3 && i + j <= s.size(); j++){
            k = k * 10 + (s[i + j -1] - '0');
            if (k > 255 || to_string(k) != s.substr(i, j)) continue;
            dfs(s, i + j, path + "." + to_string(k), p+1);
        }
    }
};