class Solution {
public:
    vector<string> res;
    vector<int> segments;
    void dfs(string s, int t, int cnt){
        //  恰好划分
        if(cnt == 4){
            if(t == s.size()){
                string tmp = "";
                for(int i = 0; i < 4; i ++ ){
                    tmp += to_string(segments[i]);
                    if(i != 3)  tmp += ".";
                }
                res.push_back(tmp);
            }
            return ;
        }
        //  特判(前缀0,别出心裁)
        if(s[t] == '0'){
            segments[cnt] = 0;
            dfs(s, t + 1, cnt + 1);
        }
        // 正常情况
        int num = 0;
        for(int i = t; i < s.size(); i ++ ){
            num = num * 10 + s[i] - '0';
            //  符合条件
            if(num > 0 && num <= 255){
                segments[cnt] = num;
                dfs(s, i + 1, cnt + 1);
            }else   break;
        }
    }
    vector<string> restoreIpAddresses(string s) {
        segments.resize(4);
        dfs(s, 0, 0);
        return res;
    }
};