题解 | #数字字符串转化成IP地址#

#include <vector>
class Solution {
  public:
    bool isValid(const string& s) {
        if (s.empty() || s.length() > 3 || (s.length() > 1 && s[0] == '0')) {
            return false;
        }
        int num = 0;
        for (int i = 0; i < s.length(); i++) {
            num = num * 10 + s[i] - 48;
        }
        return num >= 0 && num <= 255;
    }
    vector<string> solve(string s, int depth) {
        vector<string> res;
        if (depth == 3) {
            if (isValid(s)) {
                res.push_back(s);
            }
            return res;
        }
        for (int i = 0; i < 3 && i < s.length(); i++) {
            if ((i > 0 && s[0] == '0') || (i == 2 && !isValid(s.substr(0, i + 1)))) {
                break;
            }
            for (auto c : solve(s.substr(i + 1, string::npos), depth + 1)) {
                c.insert(0, s.substr(0, i + 1) + ".");
                res.push_back(c);
            }
        }
        return res;
    }
    vector<string> restoreIpAddresses(string s) {
        vector<string> res = solve(s, 0);
        return res;
    }
};