代码随想录算法训练营打卡Day28 | LeetCode93 复原 IP 地址、LeetCode78 子集、LeetCode90 子集II

摘要

分割问题首先要明确如何对字符串分割，构造树形结构来分析问题。
子集问题需要收集树形结构中的每个节点，所以要将收集结果的语句放在递归终止条件之前。

LeetCode93 复原 IP 地址

93. 复原 IP 地址 - 力扣（Leetcode）

这也是一道分割字符串的问题，首先要确定分割的规则，先确定每次分割出的子串应该符合的规则：
- 每次分割出的子串的长度最多为3
- 子串中不能含有前导0
- 子串中不能含有非数字的字符
- 子串对应的整数数值在[0, 255]中
用以上的子串规则作为剪枝条件，不难写出以下函数

bool isValid(const string& s) {
    if (s.size() > 3) return false;// 长度最多为3
    if (s[0] == '0' && s.size() > 1) return false;// 不能含有前导0
    int temp = -1;
    try {
        temp = stoi(s);
    }
    catch (invalid_argument) {
        return false;// 不能含有非数字的字符
    }
    if (temp < 0 || temp > 255) return false;// 子串对应的整数数值应在[0, 255]中
    return true;
}

确定了剪枝函数，再套用回溯法的递归函数模板
- 递归函数的终止条件：整个输入字符串被分割完成且分割出的子串数量恰好为4，说明应收集答案；分割出的子串数量大于4，说明分割出的子串不能组合出合法的IP地址，应直接返回。
- 递归函数的参数列表：输入的字符串s，结果集res，当前分割出的子串列表cur，下一次分割的起始位置start，当前分割出的子串数量part。
- 单层递归的逻辑：以start作为当前子串的起始位置，i作为当前子串的终止位置，左闭右闭区间，来枚举在本层可能分割出的子串，并通过检查分割出的子串是否能组成合法IP进行剪枝。

完整的题解代码如下，采用vector<string>来暂存子串，便于回溯（直接push和pop即可，比字符串操作方便一些，但效率好像不如直接操作字符串）。注意part初始化为0，对应的是cur中的子串数量。

class Solution {
public:
    bool isValid(const string& s) {
        if (s.size() > 3) return false;
        if (s[0] == '0' && s.size() > 1) return false;
        int temp = -1;
        try {
            temp = stoi(s);
        }
        catch (invalid_argument) {
            return false;
        }
        if (temp < 0 || temp > 255) return false;
        return true;
    }
    void backtracking(const string& s, vector<string>& res,
                    vector<string>& cur, int start, int part)
    {
        if (part > 4) return;
        if (start >= s.size()) {
            if (part != 4) return;
            string temp;
            for (auto& iter : cur) {
                temp += iter;
                if (--part) temp += ".";
            }
            res.push_back(temp);
            return;
        }
        for (int i = start; i < s.size(); i++) {
            if (isValid(s.substr(start, i - start + 1))) {
                cur.push_back(s.substr(start, i - start + 1));
                backtracking(s, res, cur, i + 1, part + 1);
                cur.pop_back();
            }
        }
    }
    vector<string> restoreIpAddresses(string s) {
        vector<string> res;
        vector<string> cur;
        backtracking(s, res, cur, 0, 0);// part 初始化为 0
        return res;
    }
};

直接操作字符串的版本，注意part要初始化为1，直接操作字符串是以插入.的形式来分割的，在未插入.时，将整个串看作一个子串，所以part初始化为1。

class Solution {
public:
    bool isValid(const string& s) {
        if (s.size() > 3) return false;
        if (s[0] == '0' && s.size() > 1) return false;
        int temp = -1;
        try {
            temp = stoi(s);
        }
        catch (invalid_argument) {
            return false;
        }
        if (temp < 0 || temp > 255) return false;
        return true;
    }
    void backtracking(string& s, vector<string>& res,
                    int start, int part)
    {
        if (part > 4) return;
        if (part == 4) {
            if (isValid(s.substr(start))) res.push_back(s);// 判断最后一个子串是否合法
            return;
        }
        for (int i = start; i < s.size(); i++) {
            if (isValid(s.substr(start, i - start + 1))) {
                s.insert(s.begin() + i + 1, '.');
                backtracking(s, res, i + 2, part + 1);
                s.erase(s.begin() + i + 1);
            }
        }
    }
    vector<string> restoreIpAddresses(string s) {
        vector<string> res;
        vector<string> cur;
        backtracking(s, res, 0, 1);// part 初始化为 1
        return res;
    }
};

LeetCode78 子集

78. 子集 - 力扣（Leetcode）

这道题目与之前的区别就是要收集树形结构中的每个节点进入结果集，所以关键在于收集结果的语句要放在递归终止的语句之前。
以[1, 2, 3]为例，其子集的构造树如下图，回溯法能遍历到每个节点，所以只需要每次递归都收集结果即可。

完整的题解代码如下

class Solution {
public:
    void backtracking(vector<int>& nums, vector<vector<int>>& res,
                    vector<int>& cur, int start)
    {
        res.push_back(cur);
        if (start >= nums.size()) return;
        for (int i = start; i < nums.size(); i++) {
            cur.push_back(nums[i]);
            backtracking(nums, res, cur, i + 1);
            cur.pop_back();
        }
    }
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> res;
        vector<int> cur;
        backtracking(nums, res, cur, 0);
        return res;
    }
};

LeetCode90 子集II

90. 子集 II - 力扣（Leetcode）

本题除了要在回溯法的树形结构中的每个节点收集结果外，还要做“树层去重”。
以[1, 2, 2]为例，其子集构造的树形结构如下

在这里复习“树枝去重”和“树层去重”
- 树枝去重：为了防止使用相同的元素，每次向下搜索时，可用元素的起始位置start应向右移一位。
- 树层去重：结果集中出现重复组合的原因不是使用了相同的元素，而是在树的同一层中使用值相同的不同元素。观察子集构造的树形结构，因为树枝去重，所以有多个值相同的元素出现时，选取其中第一个元素之后得到的组合就包含了在本层中选取该元素的所有可能。例如上面的第二层的第一个1，从第二层的第一个1开始搜索得到的组合，包含了从第二层的第二个1开始搜索得到的所有组合。所以，只需要保留从第一个1搜索得到的结果即可完成树层去重。
- 对原数组进行排序的意义就在于让值相同的元素在数组中连续分布，便于去重。

完整的题解代码如下

class Solution {
public:
    void backtracking(vector<int>& nums, vector<vector<int>>& res,
                    vector<int>& cur, int start)
    {
        res.push_back(cur);
        if (start >= nums.size()) return;
        for (int i = start; i < nums.size(); i++) {
            if (i - start && nums[i - 1] == nums[i]) continue;
            cur.push_back(nums[i]);
            backtracking(nums, res, cur, i + 1);
            cur.pop_back();
        }
    }
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        vector<vector<int>> res;
        vector<int> cur;
        sort(nums.begin(), nums.end());
        backtracking(nums, res, cur, 0);
        return res;
    }
};