leetcode93. 复原 IP 地址

分析

每个ip地址只有4个数，用dfs那么最深只有四层。

class Solution {
public:
    vector<string> ans;
    vector<int> path;
    void dfs(int start,int index,string s){
        if((4-index)&&(s.length()-start)/(4-index)>3)return;//剪枝，如果剩余的字符平均分派到未分配的地址后>3直接返回
        if(index==4){
            if(start==s.size()){
                //匹配成功
                string ip;
                for(int i=0;i<path.size();i++){
                    ip+=to_string(path[i]);
                    if(i!=path.size()-1){
                        ip+=".";
                    }
                }
                ans.push_back(ip);
            }
           return ;
        }
      
        if(start==s.size()){
            return;//
        }
        if(s[start]=='0'){
            path[index]=0;
            dfs(start+1,index+1,s);//如果此时s[i]为0,直接将0加入path
        }
        int num=0;
        for(int i=start;i<s.size();i++){//一般情况，依次列举出当前的位置数字
            num=num*10+(s[i]-'0');
            if(num>0&&num<=0xff){
                path[index]=num;
                dfs(i+1,index+1,s);
            }else break;
        }
    }
    vector<string> restoreIpAddresses(string s) {
        if(s.length()>12||s.length()<4)return ans;
        path.resize(4);
        dfs(0,0,s);
        return ans;
    }
};