题解 | #数字字符串转化成IP地址#

class Solution { public: /** * * @param s string字符串 * @return string字符串vector */ // vector restoreIpAddresses(string s) { // write code here //暴力搜索 // vector vs; // for (int i = 1; i <= 3; i++) { // for (int j = 1; j <= 3; j++) { // for (int m = 1; m <= 3; m++) { // for (int n = 1; n <= 3; n++) { // if (i + j + m + n == s.length()) { // string s1 = s.substr(0, i); // string s2 = s.substr(i, j); // string s3 = s.substr(i + j, m); // string s4 = s.substr(i + j + m, n); // if(judge(s1)&&judge(s2)&&judge(s3)&&judge(s4)) // { // string res=s1+"."+s2+"."+s3+"."+s4; // vs.push_back(res); // } // } // } // } // } // } // return vs; // }

bool judge(string s)
{
    if(stoi(s)<=255)
    {
        if(s[0]!='0'||(s.length()==1&&s[0]=='0'))
            return true;
    }
    return false;
}

//回溯加剪枝
vector<string> vs;
vector<string> restoreIpAddresses(string s){
    string res="";
    dfs(s, 0, res, 0);
    return vs;
}
void dfs(string s, int index, string& res, int step)
{
    //终止条件，当index到达最后一个字符时，可以将各个字符串拼接存入vs中
    //step是记录其中的分段点的个数
    if(step==4)
    {
        //判断索引是否到达s的最后一位，如果是，则进行存储，否则表明3个分段点并没有完全分完整个s
        if(index==s.length())
        {
            //删除最后一位多余的分段点
            res.erase(res.end()-1);
            vs.push_back(res);
        }
        else
        {
            return;
        }
    }
    //先取第一个ip段
    for(int i=1;i<=3&&index<s.length();i++)
    {
        //截取ip段
        string s1 = s.substr(index, i);
        //记录更新之前的res
        string temp = res;
        //判断字符串是否合规
        if(judge(s1))
        {
            //拼接(更新)res
            res = res+s1+".";
            //如果合乎规范，进行下一个字符串(位置是index+i)的递归
            dfs(s,index+i,res,step+1);
            //回溯(将res还原到更新之前的状态)
           res=temp;
        }
    }
}

};