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

class Solution {
public:
    /**
     * 
     * @param s string字符串 
     * @return string字符串vector
     */
    vector<string> ans;
    void backtrace(string& s, int cnt, int index, string& str) { // cnt表示ip地址转换了几个节点，index表示从字符串s的开始索引s
        if(cnt==4 || index==s.size()) {
            if(cnt==4 && index==s.size())
                ans.push_back(str.substr(0, str.size() - 1));
            return;
        }
        for(int i = 1; i <= 3; i++) {
            if(index + i > s.size())
                return;
            if(s[index]=='0' && i!=1) // 第一个字节可以是‘0’
                return;
            if(i==3 && s.substr(index, i)>"255")
                return;
            str +=s.substr(index,i);
            str.push_back('.');
            backtrace(s, cnt+1, index+i, str);
            str = str.substr(0, str.size() - i - 1); // 回溯，保存原始状态
        }
    }
    vector<string> restoreIpAddresses(string s) {
        // write code here
        string res;
        backtrace(s,0,0,res);
        return ans;
    }
};