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

题目描述
现在有一个只包含数字的字符串，将该字符串转化成IP地址的形式，返回所有可能的情况。
例如：
给出的字符串为"25525522135",
返回["255.255.22.135", "255.255.221.35"].

方法一：暴力求解
求解思路
直接对所给的字符串进行枚举，因为IP地址每一个位置可能有1到3个数字，因此我们对每一个位置进行1到3字符串大小的遍历。这样既可求出所有的IP地址

解题代码

class Solution {
public:
     bool justify(string s)//参考漫漫云天自翱翔的code
     {
        if(s.size() != 1 && s[0] == '0' || stoi(s) > 255) return true;
        //这个地方判断IP地址的时候，是为了防止出现大于255的数字组合出现，
        //并且防止类似025这种类型的数字组合出现！
        return false;
     }
    vector<string> restoreIpAddresses(string s) {
        // write code here
        vector<string> ans;
        for(int i = 1;i<=3;i++)
        {   //第一位的长度
            for(int j = 1;j<=3;j++)
            {  //第二位的长度
                for(int m = 1;m<=3;m++)
                {  //第三位的长度
                    for(int n = 1;n<=3;n++)
                    {  // 第四位的长度
                         if((i+j+m+n)==s.size())
                         {
                            string s1 = s.substr(0,i);//取子串
                            string s2 = s.substr(i,j);
                            string s3 = s.substr(i+j,m);
                            string s4 = s.substr(i+j+m,n);
                            if(!justify(s1)&&!justify(s2)&&!justify(s3)&&!justify(s4))
                            {
                                string tt = s1 + "." +s2 +"." +s3 +"." +s4;  //拼接
                                ans.push_back(tt);//将所有结果进行保存，最后输出结果。
                            }
                        }    
                    }
                }
            }
        }
        return ans;
    }
};

复杂度分析
时间复杂度：因为四个遍历都是从1到3的循环，为常数，因此为O(1)
空间复杂度：使用子串，空间复杂度为O(1)

方法二：递归的思想
求解思路
使用递归的思想，把数字字符串进行分割，然后在分割的基础上面继续分割，如果遇到不符合IP地址的格式，则这一“分支”的递归就结束，然后再看其他分割的结果。
其中参考杭电 De梦的终止条件和段位合法性，我们有：当IP地址的点的数量达到3个时，停止递归。对于段位的合法性，可以参考方法一的暴力法求解，即不能出现格式不符合IP地址的数字组合。

解题代码

class Solution {
private:
    vector<string> result;// 记录结果 参考杭电 De梦的code
    void backtracking(string& s, int startIndex, int pointNum)//startIndex:搜索的起始位置，pointNum:添加逗点的数量
    {
        if (pointNum == 3) 
        { // 逗点数量为3时，分隔结束
            // 判断第四段子字符串是否合法，如果合法就放进result中
            if (isValid(s, startIndex, s.size() - 1)) 
            {
                result.push_back(s);
            }
        }
        for (int i = startIndex; i < s.size(); i++) 
        {
            if (isValid(s, startIndex, i)) 
            { // 判断 [startIndex,i] 这个区间的子串是否合法
                s.insert(s.begin() + i + 1 , '.');  // 在i的后面插入一个逗点
                pointNum++;
                backtracking(s, i + 2, pointNum);   // 插入逗点之后下一个子串的起始位置为i+2
                pointNum--;                         // 回溯
                s.erase(s.begin() + i + 1);         // 回溯删掉逗点
            } else break; // 不合法，直接结束本层循环
        }
    }
    bool isValid(const string& s, int start, int end) 
    {
        if (start > end) 
        {
            return false;// 判断字符串s在左闭又闭区间[start, end]所组成的数字是否合法
        }
        if (s[start] == '0' && start != end) 
        { 
                return false;//0开头不合法
        }
        int num = 0;
        for (int i = start; i <= end; i++) 
        {
            if (s[i] > '9' || s[i] < '0') //非正整数字符不合法
            { 
                return false;
            }
            num = num * 10 + (s[i] - '0');
            if (num > 255) // 段位值大于255不合法
            {
                return false;
            }
        }
        return true;
    }
public:
    vector<string> restoreIpAddresses(string s) {
        result.clear();
        if (s.size() > 12) return result;
        backtracking(s, 0, 0);
        return result;
    }
};

复杂度分析
时间复杂度：递归所消耗的时间，为O( )(参考De 梦)
空间复杂度：递归使用的空间，O(N)