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

#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return string字符串vector
     */
     bool isValid(string& part)//选取的字符串是否有效
     {
        if(part.empty()||part.size()>3)//如果长度为空或者长度大于3，则无效
        {
            return false;
        }
        if(part[0]=='0'&&part.size()>1)////如果长度大于1，出现前导为0则无效
        {
            return false;
        }
        int num=stoi(part);
        if(num<0||num>255)//如果超过255或者小于0也是无效
        {
            return false;
        }
        return true;
     }
     void BackTrack(string s,int start,vector<string>& temp,vector<string>& res)
     {
         if(temp.size()==4)//已经选了4段
         {
            if(start==s.size())//s里的都选完了
            {
                string ip=temp[0]+'.'+temp[1]+'.'+temp[2]+'.'+temp[3];
                res.push_back(ip);
            }
            return;
         }

         int nextstart=s.size()-start;//剩余的字符串数目
         int remain=4-temp.size();//一个ip共4段，还剩几段
         if(nextstart<remain||nextstart>remain*3)//如果剩余的字符串数目比剩余的段数还小，即便是都选1位也不够或者剩余太多，即便是都选3位也不够
         {
            return;
         }
         for(int len=1;len<=3&&start+len<=s.size();len++)//选取1、2、3位都试试，并且保证选取的长度不要越界
         {
             string part=s.substr(start,len);//从起始位置start开始，选取len个字符构成字符串
             if(isValid(part))
             {
                temp.push_back(part);
                BackTrack(s,start+len, temp, res);
                temp.pop_back();
             }
         }


     }
    vector<string> restoreIpAddresses(string s) {
        // write code here
        vector<string> res;
        if(s.size()==0)
        {
            return res;
        }
        vector<string> temp;
        BackTrack(s,0,temp,res);
        return res;
    }
};