LeetCode 93 复原IP地址

93.复原IP地址

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

例如：0.1.2.201 和 192.168.1.1 是 有效 IP 地址，但是 0.011.255.245、192.168.1.312 和 192.168@1.1 是 无效 IP 地址。

给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 ‘.’ 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。

回溯

本题实际上就是向一个数字字符串中加入三个 . 使得最终的结果满足IP地址的定义。对于IP地址的要求为 0-255，并且要求不包含前导的0元素。此处的处理方式和 131.分割回文串 类似，也可以生成相应的IP判断二维数组，但是相应的子串是否符合IP地址的定义并不需要使用动态规划法进行判断。

创建是否满足IP的数组将导致空间复杂度的上升，因此此处也可以采取生成相应的子串后再判断的方式。

基本思路：首先，将 s[cur] 处的的子串作为IP地址中的一段，并判断是否符合规范，符合规范，tmp.push_back(s.substr(cur,1)) ，开始递归 cur+1 ，递归返回后， tmp.pop_back 完成回溯。然后选取 s[cur:cur+1] 处的作为子串，判断是否为IP

class Solution {
public:
    vector<string> res;
    vector<string> tmp;
    bool transform(string a){
        if(a.size()>1&&a[0]=='0') return false;
        istringstream is(a);
        int num;
        is>>num;
        return num<256&&num>-1;
    }
    void DFS(string s,int cur){
        if(tmp.size()==4){
            if(cur==s.size()){
                string a;
                for(auto &c:tmp)
                    a+=(c+'.');
                a.pop_back();
                res.push_back(a);
            }
            return;
        }
        if(s[cur]=='0'){
            tmp.push_back("0");
            DFS(s,cur+1);
            tmp.pop_back();
            return;
        }
        for(int i=cur;i<s.size();i++){
            if(transform(s.substr(cur,i-cur+1))){
                tmp.push_back(s.substr(cur,i-cur+1));
                DFS(s,i+1);
                tmp.pop_back();
            }
        }
    }
    vector<string> restoreIpAddresses(string s) {
        if(s.size()>12||s.size()<4) return res;
        DFS(s,0);
        return res;
    }
};