【C++】24行剪枝dfs

实际上这就是个dfs，对于每个字符有两种可能，一种是在后面加小数点，一种是不加，通过剪枝和条件判断来获得我们想要的结果

class Solution {
public:
    vector<string> res; //记录最终结果
    string str; 
    vector<string> restoreIpAddresses(string s) {
        str = s; //将s作为全局变量好操作
        helper("", 0, 0, 0);
        return res;
    }
    void helper(string cur, int num, int left, int point) { //cur是当前字符串，num是当前数字（起始为0），left是当前字符指针，point是小数点数量
        if(point >= 4) return; //排除4个小数点的情况
        if(left == str.size()) { //当指针走完
            if(point == 3) res.push_back(cur); //有3个小数点的字符串才能加入结果
            return;
        }
        int bit = str[left] - '0'; //当前字符转换为数字
        num *= 10; num += bit; //加在当前数字后
        if(num <= 255) { //剪去当前数字大于255的分支
            cur += str[left]; //不管加不加小数点都要先把当前字符加在当前字符串后面
            if(left < str.size() - 1) helper(cur + '.', 0, left + 1, point + 1); //最后一位后面不能加小数点
            if(num > 0 || (num == 0 && left == str.size() - 1)) helper(cur, num, left + 1, point); //num大于0保证了不会出现两个0没有用小数点分割开的情况，但是当0在末尾时是个特例
        }
    }
};