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

class Solution {
public:
    vector<string> res;
    string src_str;
    int str_len;
    
    string trans(vector<string> str_vec){
        string res;
        for(auto s: str_vec){
            res += s;
            res.push_back('.');
        }
        res.pop_back();    
        return res;
    }
    
    bool is_legal_num(string num_str){
        if(num_str.size()>= 2 && num_str[0] == '0'){
            return false;
        }
        int num = atoi(num_str.c_str());
        return num >= 0 && num <= 255;
    }
    
    void dfs(int index, string num_str, vector<string> tmp){
        if(index > str_len){
            return;
        }
        
        if(index < str_len && tmp.size() == 4){
            return;
        }
        if(index == str_len && tmp.size() == 4){
            res.push_back(trans(tmp));
        }
        num_str.push_back(src_str[index]);
        if(is_legal_num(num_str)){
            dfs(index+1, num_str, tmp); //不用'.'分割，继续尝试加入下一个数字到当前段。
                
            tmp.push_back(num_str); //用'.'分割，组下一段数组
            dfs(index+1, "", tmp);
            tmp.pop_back();
        }else{
            return;
        }
        num_str.pop_back();
        
    }
    /**
     * 
     * @param s string字符串 
     * @return string字符串vector
     */
    vector<string> restoreIpAddresses(string s) {
        // write code here
        src_str = s;
        str_len = src_str.size();
        if(str_len < 4 || str_len > 12){
            return res;
        }
        dfs(0, "", vector<string>());
        return res;
    }
};