93.复原IP地址

class Solution {
public:
    vector<string>res;string cur;string s;void bt(int start,int cnt){
        if(cnt==4||start>=s.size()){if(cnt==4&&start==s.size())res.push_back(string(cur.begin(),cur.end()-1));return;}
        for(int i=1;i<=3;i++){
            string sub=string(s.begin()+start,s.begin()+start+i);
            if(valid(sub)){
                auto l=cur.size();
                cur+=sub+".";
                bt(start+i,cnt+1);
                cur.erase(l);
            }
        }
    }
    bool valid(string s){
        if(s.size()==0)return false;
        if(s[0]=='0')return s.size()==1;
        int a=stoi(s);return a>=0 && a<=255;
    }
    vector<string> restoreIpAddresses(string s) {this->s=s;
        bt(0,0);return res;
    }
};