【打卡】LeetCode 93 复原IP地址：

[Medium]

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

有效的 IP 地址正好由四个整数（每个整数位于 0 到 255 之间组成），整数之间用 ‘.’ 分隔。

示例:

输入: “25525511135”
输出: [“255.255.11.135”, “255.255.111.35”]

#include<string>
#include<vector>
using namespace std;

class Solution {
private:
    vector<string> res;
    vector<string> tmp_res;
public:
    void dfs(string &s,int start,int level){
        //
        if(level==5){
            string s_tmp;
            for(int i = 0;i<4;i++){
                if(i!=0)s_tmp+=".";
                s_tmp+=tmp_res[i];
            }
            res.push_back(s_tmp);
            return ;
        }
        if(start>=s.size())return;
        for(int len = 1;len<=3;len++){
            if(len>1&&s[start]=='0')break;
            int remain_len = s.size()-(start+len);
            if(remain_len>(4-level)*3)continue;
            if(remain_len<(4-level))continue;
            int val = stoi(s.substr(start,len));
            if(val<=255){
                tmp_res.push_back(s.substr(start,len));
                dfs(s,start+len,level+1);
                tmp_res.pop_back();
            }
        }
    }
    vector<string> restoreIpAddresses(string s) {
        dfs(s,0,1);//从第i个位置开始迭代
        return res;
    }
};