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

class Solution {
public:
    vector<string> restoreIpAddresses(string s) {
        vector< string > ans={};
        string temp="";
        int count=0;
        dp(0, s, ans, temp, 0);
        return ans;
    }

    void dp(int index, string& s, vector<string>& ans, string& temp, int count){
        if( count == 4 && index == s.size()){ //完成
            temp.pop_back();  //弹出最后的点
            ans.push_back(temp);
            return;
        }
        if(count>= 4 || index >= s.size()){  //当达到节数却没有达到最后，或者超过字符串却没有达到节数；
            return;
        }


        for(int i=index; i<=index+2 && i<s.size() ; i++){ //
            string sub_s = s.substr(index, i-index+1);
            if(sub_s.size() > 1 && sub_s.front() == '0'){  //0x、00，当出现前导0并且大于一位时，数字不符合规则；
                return;
            }
            int val_sub_s = stoi(sub_s);  //获得数字
            if(val_sub_s <= 255 ){  
                temp = temp + sub_s + ".";
            }else{  //超出每节的范围
                continue;
            }

            count++;
            dp(i+1, s, ans, temp, count);
            //回溯
            count--;
            temp.pop_back(); //弹出点
            while(!temp.empty() && temp.back() != '.'){ //弹出数字
                temp.pop_back();
            }
        }

        return;
    }
};