93. Restore IP Addresses

Given a string containing only digits, restore it by returning all possible valid IP address combinations.

Example:

Input: "25525511135"
Output: ["255.255.11.135", "255.255.111.35"]

// Backtracking
void helper(string s, int n, string cur, vector<string>& res) {
    if (n == 4) {
        if (s.empty()) res.push_back(cur);
        return;
    }
    for (int i = 1; i <= 3; ++i) {
        if (s.length() < i) break;
        int val = stoi(s.substr(0, i));
        if (val > 255 || std::to_string(val).length() != i) continue;
        helper(s.substr(i), n + 1, cur + s.substr(0, i) + (n == 3 ? "" : "."), res);
    }
}
vector<string> restoreIpAddresses(string s) { // time: O(3^n); space: O(3^n)
    vector<string> res;
    helper(s, 0, "", res);
    return res;
}

// Backtracking
bool isValid(const string& s) {
    if (s.empty() || s.length() > 3 || (s.length() > 1 && s[0] == '0')) return false;
    int num = stoi(s);
    return num >= 0 && num <= 255;
}
void helper(string s, int k, string str, vector<string>& res) {
    if (k == 0) {
        if (s.empty()) res.push_back(str);
        return;
    }
    for (int i = 1; i <= 3; ++i) {
        if (s.length() >= i && isValid(s.substr(0, i))) {
            string new_str = str + s.substr(0, i) + (k == 1 ? "" : ".");
            helper(s.substr(i), k - 1, new_str, res);
        }
    }
}
vector<string> restoreIpAddresses(string s) { // time: O(3^n); space: O(3^n)
    vector<string> res;
    helper(s, 4, "", res);
    return res;
}