[Lc]93复原IP地址

题目

题解

这道题主要是递归然后剪枝，符合条件的放入结果，不符合就键值，主要是要确定几种不符合条件的情况

• 剩下的数字不够分的，比如还有2个数，但是还有3个ip整数位，剪枝
• 剩下的数字超出范围，比如还剩7个数，但是只剩2个ip整数位了，放不下了，直接剪枝
• 当前这一位超过255，剪枝
• 这一位数字多于一位且首位为0，剪枝

string转int总结见[我的另一篇博客]

class Solution {
public:
    void DFS(string s, int level, string out, vector<string>& res){
        if(s.size() < (4-level) || s.size() > (4-level)*3) return;//前两种特殊情况，出现直接剪枝
        if(level == 4 && s.empty()){
            res.emplace_back(out);
            return;
        }//深度到第四层说明已经且s空了，说明这个out已经放完了所有数字，符合结果，可以加入res
        for(int i=1; i<4; i++){//每个节点有三个分支，即1个数，2个数，3个数
            if(s.size() < i) break;//若i已经大于了s的长度，直接剪枝，后面循环的枝都剪掉，跳出循环
            //int val = atoi(s.substr(0,i).c_str());
            int val = stoi(s.substr(0,i));//两种将string转为int的方式
            //若val>255或者多位数字第一个数字为为0（即val再转换为str长度改变），剪枝
            if(val > 255 || i != to_string(val).size()) continue;
            //进行递归
            DFS(s.substr(i), level+1, out+to_string(val)+(level==3? "":"."), res);
        }
    }

    vector<string> restoreIpAddresses(string s) {
        vector<string> res;
        if(s.empty()) return res;//特殊情况
        DFS(s, 0, "", res);//深度优先遍历
        return res;
    }
};