LeetCode-93-复原IP地址

给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。

示例:

输入: "25525511135"
输出: ["255.255.11.135", "255.255.111.35"]

Code

class Solution {
public:
    vector<string> res;
    vector<string> restoreIpAddresses(string s) {
        //预处理，长度为12，只有一种结果，直接返回
        if(s.length()==12){
            for (int j = 0;j <4;j+=3) {
                string str = s.substr(j, 3);
                if (str[0] == '0' || stoi(str) > 255)
                    return res;
            }
            for(int i=3;i<=11;i+=4)
                s.insert(i,".");
            res.push_back(s);
            return res;
        }
        //递归dfs处理字符串
        dfs(s,"",0,0);
        return res;
    }

    void dfs(string s,string temp,int index,int count){
        //记录递归的层数
        if(count>4)return;
        if(count==4&&index==s.length())
            res.push_back(temp);
        for(int i=1;i<4;i++){
            if(index+i>s.length())return;
            string str = s.substr(index,i);
            //stoi(str)将字符串转为数字
            if((str.length()>1&&str[0]=='0')||stoi(str)>255)
                return;
            dfs(s,temp+str+(count==3?"":"."),index+i,count+1);

        }
    }
};