Description

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"]

Solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

class Solution {
public:
    Solution() : _empty(""), _dot(".") {
    }

    vector<string> restoreIpAddresses(string s) {
        vector<string> result;

        solve(result, "", 0, s);

        return result;
    }

    void solve(vector<string> &result, string ip, int n, string s) {
        size_t len = s.length();

        if (n == 4 ) {
            if (len == 0) {
                result.push_back(ip);
            }
            return;
        }

        string &mid = n > 0 ? _dot : _empty;

        int cur = 0;
        for (size_t i = 0; i < len; i++) {
            cur = cur*10 + static_cast<int>(s.at(i) - '0');
            if (cur > 255) {
                return;
            }

            solve(result, ip + mid + s.substr(0, i+1), n + 1, s.substr(i+1));

            if (cur == 0) {
                return;
            }
        }
    }

private:
    string _empty;
    string _dot;
};