class Solution {
public:
    vector<string> result;
    vector<string> path;
    //判断是合法IP
    bool cheak(string &s)
    {
        if(s.size()==0)return false;
        if(s.size() > 1 && s[0]=='0') return false;
        if (stoi(s) > 255) return false;
        return true;
    }
    void back_tracking(string &s , int indnx )
    {
      //IP最大短是4
        if(path.size() > 4)  return;
        //循环指针大于等于长度，并且IP段为四段。合法IP
        if(indnx >= s.size() && path.size()==4)
        {
            string tmp;
            for(int i=0 ;i< path.size()-1 ;i++)
            {
                tmp += path[i];
                tmp += '.';
            }
            tmp += path[path.size()-1];
            result.push_back(tmp);
            return;
        }
    //循环输入字符串，从index开始截取IP段
        for(int i=indnx ; i<s.size() ;i++)
        {
            string tmp;
            //截取一个IP段，但是不超过3位
            for(int j = indnx ; j<=i  &&  (j-indnx)<=3 ;j++)
            {
                tmp += s[j];
            }
      //检测是否为合法段，合法压入路径，不合法跳过该段
            if(cheak(tmp)==1) path.push_back(tmp);
            else continue;
      //递归
            back_tracking(s,i+1);
            //回溯
            path.pop_back();
        }
        return;
    }
    vector<string> restoreIpAddresses(string s) {
        back_tracking(s,0);
        return result;
    }
};

class Solution {
public:
    vector<string> result;
    vector<string> path;
    bool cheak(string s)
    {
        if(s.size() > 1 && s[0]=='0' || s.size() > 3) return false;
        int num = stoi(s);
        if(num > 255 || num <0) return false;
        return true;
    }
    void track_back(string s , int indnx)
    {
        if(path.size() > 4) return;
        if(indnx >= s.size() && path.size()==4) 
        {
            string tmp;
            for(int i=0 ; i<3 ;i++)
            {
                tmp += path[i];
                tmp += ".";
            }
            tmp += path[3];
            result.push_back(tmp);
        }
        for(int i= indnx ; i<s.size()&&i<indnx+3 ;i++)
        {   
            string tmp_ip = s.substr(indnx,i-indnx+1);
            if(cheak(tmp_ip) == false) continue;
            else
            {
                path.push_back(tmp_ip);
                track_back(s,i+1);
                path.pop_back();
            }
        }
    }
    vector<string> restoreIpAddresses(string s) {
        track_back(s,0);
        return result;
    }
};