Description

Submission

class Solution {
    unordered_set<string> ips;
    vector<string> hand;

    string s;

    // pos: the dot is after pos
    // prev: the prev dotf
    void dfs(int pos) {
        if(hand.size() == 4) {
            if(pos == s.size()) {
                ips.insert(hand[0] + "." + hand[1] + "." + hand[2] + "." + hand[3]);
            }
            return;
        }
    
        for(int i = 1; i <= 3 && pos+i <= s.length(); ++i) {
            int t = stoi(s.substr(pos, i));
            if(t <= 255) {
                string sub = to_string(t);
                if(sub.length() != i) break;

                hand.push_back(sub);
                dfs(pos+i);
                hand.pop_back();
            }
        }
    }

public:
    vector<string> restoreIpAddresses(string s) {
        this->s = s;

        dfs(0);

        return {ips.begin(), ips.end()};
    }
};