93. 复原IP地址

93. 复原IP地址

搜索+剪枝

class Solution {
public:
    vector<string> res;

    void dfs(int u, string s, int num, string path) {
        if (num == 4 && s.size())return;
        else if (num == 4 && s.size() == 0) {
            res.push_back(path.substr(1));
            return ;
        }

        for (int i = 0; i < 3; i++) {
            if(s.size()<i+1)continue;
            string tmp = s.substr(0, i + 1);
            int tt = stoi(tmp);
            if (tt > 255)continue;
            if(tmp.size()>=2 && tmp[0]=='0') return ;
            string newpath=path + "." + tmp;
            dfs(i + 1, s.substr(i + 1), num + 1, newpath);
        }
    }

    vector<string> restoreIpAddresses(string s) {
        dfs(0, s, 0, "");
        return res;
    }
};