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

回溯法

class Solution {
public:
    /**
     * 
     * @param s string字符串 
     * @return string字符串vector
     */
    bool judge(string str){  //判断地址中的单元是否合法
        if(str.size()==0) return false;
        if(str[0]=='0'&&str.size()>1) return false;
        int res=0,num=0;
        for(int i=0;i<str.size();i++){
            res=res*10+(str[i]-'0');
        }
        if(res>255) return false;
        return true;
    }
    void help(vector<string> &res,string str,string s,int start,int num){
        if(start==s.size()&&num==4){ //如果遍历完了字符串，并且有4个合法单元，就加入res
            //cout<<str<<endl;
            str.pop_back();
            res.push_back(str);
            return ;
        }
       for(int i=1;i<=3&&start+i<=s.size();i++){  //模拟单元字符串的长度
            string temp=s.substr(start,i);
            if(judge(temp)&&num<4){
                str+=temp;
                str.push_back('.');
                help(res,str,s,start+i,num+1);
                for(int j=0;j<=i;j++) str.pop_back(); //回溯
            }
        }
        return ;
    }
    vector<string> restoreIpAddresses(string s) {
        // write code here
        vector<string> res;
        string str;
        help(res,str,s,0,0);
        return res;
    }
};