LeetCode 93. Restore IP Addresses [Medium] [C++] 解題筆記

這題給定一個只由數字組成的 string s，要我們求 s 可能形成的所有合法的 IP address。

EX:

        Input: "25525511135"

    Output: ["255.255.11.135", "255.255.111.35"]

想法:

    這題我一看到直覺就是用 dfs ，因為要形成 IP address 需要將 s 分割成 4 個部份，那問題其實就可以想成

要選 3 個位置插入 "."，因此只要用 dfs 搜索 "." 可能的位置並將不可能的分支做剪枝即可。

完整程式碼:

class Solution {
public:
    vector<string> res;
    bool isVaild(string_view s) {
        if (s.length() > 3) { return false; }
        if (s[0] == '0' && s.length() > 1) { return false; }
        const int len = s.length();
        int value = 0;
        for (int i = len - 1; i >= 0; i--) {
            value += (s[i] - '0') * pow(10, (len - i - 1));
        }
        return (value > 255)? false : true;
    }
    void dfs(string_view s, int deep, vector<int>& cur) {
        if (deep > 4) { return; }
        if (deep == 4) {
            if (isVaild(s.substr(cur.back()))) {
                string tmp = string(s).c_str();
                for (int i = 0; i < cur.size(); i++) {
                    tmp.insert(cur[i] + i, ".");
                }
                res.emplace_back(tmp);
            }
            return;
        }
        int last_start = cur.empty()? 0 : cur.back();
        for (int i = last_start + 1; i < s.size(); i++) {
            if (isVaild(s.substr(last_start, i - last_start))) {
                cur.push_back(i);
                dfs(s, deep + 1, cur);
                cur.pop_back();
            }
        }   
        return;
    }
    vector<string> restoreIpAddresses(string s) {
        vector<int> cur;
        dfs(s, 1, cur);
        return res;
    }
};