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

回溯分割字符串。用'.'的个数作为递归返回条件。

class Solution {
public:
    /**
     * 
     * @param s string字符串 
     * @return string字符串vector
     */
    bool is_valid(const string& s,int start,int end){
        if(start>end) return false;
        if(s[start]=='0' && start!=end) return false;
        int val=0;
        for(int i=start;i<=end;i++){
            if(s[i]>'9' || s[i]<'0') return false;
            val=10*val + (s[i]-'0');
            if(val>255) return false;
        }
        return true;
    }
    
    void backtrack(string& s,vector<string>& result,int index,int points){
        if(points==3){
            if(is_valid(s, index, s.size()-1)) result.push_back(s);
            return;
        }
        for(int i=index;i<s.size();i++){
            if(is_valid(s, index, i)){
                s.insert(s.begin()+i+1, '.');
                points++;
                backtrack(s, result, i+2, points);
                points--;
                s.erase(s.begin()+i+1);
            }
            else break;
        }
    }
    
    vector<string> restoreIpAddresses(string s) {
        vector<string> result{};
        backtrack(s, result, 0, 0);
        return result;
    }
};