restore-ip-addresses

//IP地址每个字段可能是1位数，2位数或者3位数，每一个字段都位于1~255之间

class Solution {
public:
    vector<string> restoreIpAddresses(string s) {
        vector<string>res;
        dfs(s,0,"",res);
        return res;
    }
    void dfs(string s,int n,string out,vector<string>&res)
    {
        if(s.size()==0&&n==4)
        {
            res.push_back(out);
            return;
        }
        for(int k=1;k<4;k++)
        {
            if(s.size()<k)return;
            int value=atoi(s.substr(0,k).c_str());
            if(value>255||k!=to_string(value).size())return;//出现0x之后，后面的都是0xxxxx，都不合法
            dfs(s.substr(k),n+1,out+s.substr(0,k)+(n==3?"":"."),res);
        }
    }
};