LeetCode_Archiver/LeetCode/cpp/93.cpp at master · chr1sc2y/LeetCode_Archiver · GitHub

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
class Solution {
public:
    vector<string> restoreIpAddresses(string s) {
        int n = s.size();
        vector<string> ret;
        vector<int> temp;
        BackTracking(s, n, 0, temp, ret);
        return ret;
    }

    void BackTracking(string &s, int &n, int i, vector<int> &temp, vector<string> &ret) {
        if (temp.size() == 4) {
            if (i == n)
                push(temp, ret);
            return;
        }
        for (int j = i; j < i + 3; ++j) {
            if (j >= n) return;
            if (stoi(s.substr(i, j - i + 1)) > 255) return;
            if (j - i > 0 && s[i] == '0') return;
            temp.push_back(stoi(s.substr(i, j - i + 1)));
            BackTracking(s, n, j + 1, temp, ret);
            temp.pop_back();
        }
    }

    void push(vector<int> &temp, vector<string> &ret) {
        string s;
        for (int i = 0; i < 4; ++i)
            s += (to_string(temp[i]) + ".");
        s.pop_back();
        ret.push_back(s);
    }
};