Problem

Given a string containing only digits, restore it by returning all possible valid IP address combinations.
IP addresses are represented in dot-decimal notation, for example: "192.168.1.1".
Example input: "25525511135"
Example output: ["255.255.11.135", "255.255.111.35"]

Solution

#include <iostream>
#include <string>
#include <vector>

using namespace std;

vector<string> restoreIpAddresses(string s) {
    vector<string> res;
    int len = s.size();
    for (int i = 1; i < 4 && i < len - 2; i++) {
        for (int j = i + 1; j < i + 4 && j < len - 1; j++) {
            for (int k = j + 1; k < j + 4 && k < len; k++) {
                string s1 = s.substr(0, i), s2 = s.substr(i, j - i), s3 = s.substr(j, k - j), s4 = s.substr(k, len - k);
                if (isValid(s1) && isValid(s2) && isValid(s3) && isValid(s4)) {
                    res.push_back(s1 + "." + s2 + "." + s3 + "." + s4);
                } }
        }
    }
    return res;
}

bool isValid(string s) {
    if (s.size() > 3 || s.size() == 0 || (s.size() > 1 && s[0] == '0') || stoi(s) > 255) return false;
    return true;
}

int main() {
    string s = "25525511135";
    vector<string> res = restoreIpAddresses(s);
    for (int i = 0; i < res.size(); i++) {
        cout << res[i] << endl;
    }
    return 0;
}