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

用回溯算法来解决这个问题，需要注意的是一些细节，定义出什么时候认为是正确的答案；

class Solution {
private:
    string path = "";
    vector<string> res;
public:
    /**
     * 
     * @param s string字符串 
     * @return string字符串vector
     */
    vector<string> restoreIpAddresses(string s) {
        // write code here
        dfs(s, 0, 0, 0);
        return res;
    }
    
    void dfs(string s, int left, int num, int point_num){
        if(path.size() > (s.size()+4)){
            return;
        }
        if(left == s.size() && num == 4){
            string b = path;
            b.pop_back();
            res.push_back(b);
            return;
        }
        
        if(num > 4 || point_num >= 4){
            return;
        }
        
        for(int i=0; i<3; i++){
            if(left+i > s.length()){
                continue;
            }
            string temp = s.substr(left, i+1);
            bool a = check(temp);
            if(a == false){
                continue;
            }
            string st1 = path;
            path += temp;
            path.push_back('.');
            dfs(s, left+i+1, num+1, point_num+1);
            path.pop_back();
            path = st1;
        }
        
    }
    
    bool check(string s){
        if(s.length() >= 4){
            return false;
        }
        if(s.length() > 1 && s[0] == '0'){
            return false;
        }
        int res = 0;
        for(int i=0; i<s.length(); i++){
            res = res * 10 + (s[i] - '0');
        }
        
        if(res > 255){
            return false;
        }
        
        return true;
    }
    
};