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

简单回溯

class Solution {
public:
    /**
     * 
     * @param s string字符串 
     * @return string字符串vector
     */
    vector<string> restoreIpAddresses(string s) {
        // write code here
        helper(s, 0, s.length(), 0);
        return res;
    }
    vector<string> res;
    string ip;
    void helper(string s, int i, int n, int cnt){
        if(i == n && cnt == 4){
            res.push_back(ip);
            return;
        }
        if(cnt > 4) return;
        int val = 0;
        for(int j = i; j < n && j <= i + 2; j ++){
            if(j != i && val == 0) break; //不能有连续0或者0开头
            val = val * 10 + s[j] - '0';
            if(val <= 255){
                string ss = to_string(val);
                ip += ss;
                if(j != n - 1) ip += '.';
                helper(s, j + 1, n, cnt + 1);
                if(j != n - 1) ip.erase(ip.length() - 1, 1);
                ip.erase(ip.length() - ss.length(), ss.length());
            }
        }
    }
};