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

题解一：暴力法
题解思路： 暴力去枚举4个位置所占的位数，按照题目要求对每个位置的值进行合法性判断（0<=x<=255)
不合法判断： 1.占的位数不为1，但是其第一位上的值为0； 2. 大于255的
复杂度分析：
时间复杂度：O(1) 每层循环都是常数级
空间复杂度：O(1)

实现如下：

class Solution {
public:
    /**
     *
     * @param s string字符串
     * @return string字符串vector
     */
     bool justify(string s){
        if(s.size() != 1 && s[0] == '0' || stoi(s)> 255) return true;  //长度不为1且第一位为0 或者>255
        return false;
    }
    vector<string> restoreIpAddresses(string s) {
        // write code here
        vector<string> ans;
        for(int i = 1;i<=3;i++){   //第一位的长度 由于合法值在[0-255],所以最多长度为3
            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;
    }
};

题解二：递归回溯
题解思路：使用index表示下一个数在字符串s的起始位置，tmp表示已经切分的个数
递归边界： 已经分为4段了，且合法（tmp.size()==4）
回溯阶段： 将加入到tmp中的删除，且index要复原
判断合法： 1. index不能越界 2. num <=255 3 . 长度不为1且s[index] 不为0

图示：

复杂度分析：
时间复杂度：O(3^N) :每个循环都是常数级 N = 4
空间复杂度; O(N)

实现如下：

class Solution {
public:
    /**
     * 
     * @param s string字符串 
     * @return string字符串vector
     */
     void solve(string s,vector<string>& ans,vector<string> tmp,int index){
        if(tmp.size()!=4&&index == s.size()) return;  //越界判断
        if(tmp.size()==4) {encode(tmp,ans,s);return;} 
        for(int i = 1;i<=3;){   
            int num = stoi(s.substr(index,i));
            if(num>255||i>1 && s[index]=='0') break;  //合法判断
            tmp.push_back(s.substr(index,i));  //分段
            index += i;   //下一段的起始位置
            solve(s, ans,tmp, index);
            index -= i;   //index复原
            tmp.pop_back();  //删除上次添加的
            if(i+index<s.size()) i++;  
            else break;
        }
    }
    void encode(vector<string> tmp,vector<string> &ans,string s){
        string s1="";
        //拼接

        for(int i = 0;i<tmp.size()-1;i++){
            s1 += tmp[i]+'.';
        }
        s1 += tmp[tmp.size()-1]; 
        //拼接之后的字符串长度只比原字符串多3

        if(s.size() == s1.size()-3)
            ans.push_back(s1);
    }
    vector<string> restoreIpAddresses(string s) {
        // write code here
        vector<string> ans;
        solve(s,ans,vector<string>(),0);
        return ans;
    }
};