C++ 解法, 执行用时: 2ms, 内存消耗: 332KB, 提交时间: 2021-05-18

class Solution {
public:
    vector<string> str_vec;
    string str;   int len;
    /**
     * 
     * @param s string字符串 
     * @return string字符串vector
     */
    vector<string> restoreIpAddresses(string s) {
        // write code here
        str_vec.clear();
        len = s.length();   swap(str, s);
        DFS(0, 0, "");
        
        return str_vec;
    }
    
    void DFS(int idx, int part, string tmp_str)
    {
        if(idx == len){
            if(part == 4){
                tmp_str.pop_back();   str_vec.push_back(tmp_str);
            }
            return ;
        }
        if(len-idx > (4-part)*3) return ;
        
        part++;
        
        if(str[idx] == '0'){ DFS(idx+1, part, tmp_str+"0.");   return ; }
        
        int val( str[idx]-'0' );
        tmp_str += str[ idx++ ];
        DFS(idx, part, tmp_str+'.');
        
        if(idx == len) return ;
        val = val*10 + str[idx]-'0';
        tmp_str += str[ idx++ ];
        DFS(idx, part, tmp_str+'.');
        
        if(idx == len) return ;
        if((val = val*10 + str[idx]-'0') > 255) return ;
        DFS(idx+1, part, tmp_str+str[idx]+".");
    }
};

C++ 解法, 执行用时: 2ms, 内存消耗: 336KB, 提交时间: 2021-04-12

class Solution {
public:
    /**
     * 
     * @param s string字符串 
     * @return string字符串vector
     */
    vector<string> restoreIpAddresses(string s) {
        // write code here
        vector<vector<int>> res;
        vector<int> cur;
        dfs(s,0,cur,res);
        vector<string> sres;
        for(int i=0;i<res.size();++i)
        {
            vector<int> temp=res[i];
            string stemp;
            for(int j=0;j<temp.size();++j)
            {
                if(j>0)
                    stemp+=".";
                stemp+=to_string(temp[j]);
            }
            sres.push_back(stemp);
        }
        return sres;
    }
    
    void dfs(string &s,int i,vector<int> cur,vector<vector<int>> &res)
    {
        //1+
        if(i==s.size()&&cur.size()==4)
            res.push_back(cur);
        if(s.size()-i>3*(4-cur.size()))
            return;
        if(s.size()-i<(4-cur.size()))
            return;
        int a=0;
        for(int j=i;j<i+3&&j<s.size();++j)
        {
            a=a*10+(s[j]-'0');
            if(a>255)
                return;
            cur.push_back(a);
            dfs(s,j+1,cur,res);
            cur.pop_back();
            if(s[i]=='0')
                return;
        }
        
        //2+ mine
        /*int a=0;
        for(int j=i;j<i+3&&j<s.size();++j)
        {
            a=a*10+(s[j]-'0');
            if(a>255)
                return;
            cur.push_back(a);
            if(j==s.size()-1)
            {
                if(cur.size()==4)
                    res.push_back(cur);
                return;
            }
            else
            {
                if(cur.size()!=4)
                    dfs(s,j+1,cur,res);
            }
            cur.pop_back();
            if(s[i]=='0')
                return;
        }*/
        
    }
};

C++ 解法, 执行用时: 2ms, 内存消耗: 344KB, 提交时间: 2020-11-01

class Solution {
public:
    /**
     * 
     * @param s string字符串 
     * @return string字符串vector
     */
    vector<string> restoreIpAddresses(string s) {
        // write code here
        vector<string> arrResult, arrTmp;
        dfs(s, arrResult, arrTmp, 0);
        return arrResult;
    }
    
    bool isValid(string& s) {
        if((s.size() > 1 && s[0] == '0') || s.size() > 3)
            return false;
        return stoi(s) < 256;
    }
    
    void dfs(string& s, vector<string>& res, vector<string>& cur, int pos) {
        int maxSize = (4 - cur.size()) * 3;
        if(s.size() - pos > maxSize) 
            return;
        if(cur.size() == 4 && pos == s.size()) {
            res.push_back(cur[0] + '.' + cur[1] + '.' + cur[2] + '.' + cur[3]);
            return;
        }
        for(int i = pos; i < s.size(); i++) {
            string temp = s.substr(pos, i - pos + 1);
            if(isValid(temp)) {
                cur.push_back(temp);
                dfs(s, res, cur,i + 1);
                cur.pop_back();
            }
        }
    }
};

C++ 解法, 执行用时: 2ms, 内存消耗: 348KB, 提交时间: 2021-03-22

class Solution
{
public:
    /**
     * 
     * @param s string字符串 
     * @return string字符串vector
     */

    void dfs(const string &s, const int p, vector<int> &v, vector<string> &ans)
    {
        if (v.size() > 4)
            return;
        if (!v.empty() and v.back() > 255)
            return;
        if (p == s.size())
        {
            if (v.size() != 4)
                return;
             string t = "";
            for (int i = 0; i < 4; ++i)
            {
                if (i != 0)
                    t += '.';
                int num = v[i];
                string rev = "";
                if (num == 0)
                    rev += '0';
                while (num != 0)
                {
                    rev += char(num % 10 + '0');
                    num /= 10;
                }
                reverse(rev.begin(), rev.end());
                t += rev;
            }
            ans.push_back(t);
        }
        int num = s[p] - '0';

        if (!v.empty() and v.back() != 0)
        {
            v.back() = v.back() * 10 + num;
            dfs(s, p + 1, v, ans);
            v.back() = (v.back() - num) / 10;
        }

        v.push_back(num);
        dfs(s, p + 1, v, ans);
        v.pop_back();
    }

    vector<string> restoreIpAddresses(string s)
    {
        // write code here
        vector<string> ans;
        vector<int> v;
        dfs(s, 0, v, ans);
            reverse(ans.begin(), ans.end());
        return ans;
    }
};

C++ 解法, 执行用时: 2ms, 内存消耗: 348KB, 提交时间: 2020-11-05

class Solution {
public:
    vector<string> restoreIpAddresses(string s) {
        int n=s.size();
        vector<string> res;
        vector<string> cur;
        dfs(res,cur,s,0,0,n);
        return res;
    }
    void dfs(vector<string> &res,vector<string> &cur,string &s,int start,int count,int n){
        if(count==4){
            if(start==n){
                string ss=cur[0]+"."+cur[1]+"."+cur[2]+"."+cur[3];
                res.push_back(ss);
            }
            return;
        }
        for(int i=start;i<n;i++){
            if(i>start+3)
                break;
            string ss=s.substr(start,i-start+1);
            if(stoi(ss)<=255){
                if(ss.size()==1||ss[0]!='0'){
                cur.push_back(ss);
                dfs(res,cur,s,i+1,count+1,n);
                cur.pop_back();
                }
            }
        }
    }
};