LCR085-LCR087使用回溯法解决其他类型的问题

剑指offer（专项突破版）13.3 使用回溯法解决其他类型的问题

LCR085.括号生成

分析

如果输入n，那么生成的括号组合包含n个左括号和n个右括号。因此生成这样的组合需要2n步，每一步生成一个括号。每一步都面临两个选项，既可能生成左括号也可能生成右括号。由此来看，这个问题很适合采用回溯法解决。

在生成括号组合时需要注意每一步都要满足限制条件。第1个限制条件是左括号或右括号的数目不能超过n个。第2个限制条件是括号的匹配原则，即在任意步骤中已经生成的右括号的数目不能超过左括号的数目。例如，如果在已经生成”()”之后再生成第3个括号，此时第3个括号只能是左括号不能是右括号。如果第3个是右括号，那么组合变成”()）”，由于右括号的数目超过左括号的数目，之后不管怎么生成后面的括号，这个组合的左括号和右括号都不能匹配。

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> res;
        helper(n, n, "", res);
        return res;
    }
    void helper(int left, int right, string s, vector<string>& res){
        // 递归结束
        if(left == 0 && right == 0){
            res.push_back(s);
            return;
        }
        // 选择左括号
        if(left > 0){
            helper(left-1, right, s+"(", res);
        }
        // 选择右括号
        if(left < right){
            helper(left, right-1, s+")", res);
        }
    }
};

• 时间复杂度：在最坏情况下，对于一个给定的 n，递归调用次数是 Catalan number，约为$\frac{4^n}{n^\frac{3}{2}\sqrt{\pi}}$次。因此时间复杂度为$\frac{4^n}{\sqrt{n}}$。
• 空间复杂度：最多需要存储2n个字符，即O(n)。

LCR086.分割回文串

分析

当处理到字符串中的某个字符时，如果包括该字符在内后面还有n个字符，那么此时面临n个选项，即分割出长度为1的子字符串（只包含该字符）、分割出长度为2子字符串（即包含该字符及它后面的一个字符），以此类推，分割出长度为n的子字符串（即包含该字符在内的后面的所有字符）。由于题目要求分割出来的每个子字符串都是回文，因此需要逐一判断这n个子字符串是不是回文，只有回文子字符串才是符合条件的分割。分割出一段回文子字符串之后，接着分割后面的字符串。

例如，输入字符串”google”，假设处理到第1个字符’g’。此时包括字符’g’在内后面一共有6个字符，所以此时面临6个选项，即可以分割出6个以字符’g’开头的子字符串，分别为”g”、”go”、”goo”、”goog”、”googl”和”google”，其中只有”g”和”goog”是回文子字符串。分割出”g”和”goog”这两个回文子字符串之后，再用同样的方法分割后面的字符串。

解决这个问题同样需要很多步，每一步分割出一个回文子字符串。如果处理到某个字符时包括该字符在内后面有n个字符，就面临n个选项。这也是一个典型的适用回溯法的场景。通常用递归的代码实现回溯法。

class Solution {
public:
    vector<vector<string>> partition(string s) {
        vector<string> cur;
        vector<vector<string>> res;
        helper(s, 0, cur, res);
        return res;
    }
    void helper(string s, int index, vector<string>& cur, vector<vector<string>>& res){
        // 递归结束
        if(index == s.length()){
            res.push_back(cur);
            return;
        }
        // 从当前index开始，尝试每一个可能的结束索引
        for(int i = index; i < s.length(); i++){
            // 如果当前子串是回文串
            if(isPalindrom(s, index, i)){
                string str = s.substr(index, i-index+1);
                cur.push_back(str);
                helper(s, i+1, cur, res);
                cur.pop_back(); // 尝试新的结束索引
            }
        }
    }
    // 判断是否是回文子串
    bool isPalindrom(string s, int left, int right){
        while(left < right){
            if(s[left++] != s[right--]){
                return false;
            }
        }
        return true;
    }
};

举例说明：

假设字符串 s = “aab”，以下是算法的部分执行过程：

第一次递归调用：
    index = 0，cur = []
    尝试 i = 0，子串 s[0:1] = "a" 是回文：
        cur.push_back("a")，cur = ["a"]
        递归调用 helper(s, 1, ret, cur)

第二次递归调用：
    index = 1，cur = ["a"]
    尝试 i = 1，子串 s[1:2] = "a" 是回文：
        cur.push_back("a")，cur = ["a", "a"]
        递归调用 helper(s, 2, ret, cur)

第三次递归调用：
    index = 2，cur = ["a", "a"]
    尝试 i = 2，子串 s[2:3] = "b" 是回文：
        cur.push_back("b")，cur = ["a", "a", "b"]
        递归调用 helper(s, 3, ret, cur)

达到字符串末尾：
    index = 3，已达到字符串末尾，当前结果 ["a", "a", "b"] 是一个完整的回文划分：
        ret.emplace_back(cur)
        回溯，cur.pop_back()，cur = ["a", "a"]

继续回溯和尝试：
    回到第二次递归调用，继续尝试 i = 2，但是 s[1:3] = "ab" 不是回文：
        回溯，cur.pop_back()，cur = ["a"]

再回溯和继续尝试：
    回到第一次递归调用，继续尝试 i = 1，但是 s[0:2] = "aa" 是回文：
        cur.push_back("aa")，cur = ["aa"]
        递归调用 helper(s, 2, ret, cur)

• 时间复杂度：
  • 每个字符都有可能作为一个划分点，这意味着我们最多有$2^n$种不同的划分方式。这是因为每个字符前都可以选择划分或不划分，总共有n−1个位置可供选择，形成$2^(n−1)≈2^n$种组合。
  • isPalindrom 函数检查一个子串是否为回文，其时间复杂度是 O(n)，因为需要线性扫描子串的每个字符。
  • 总体的时间复杂度为$O(n \cdot {2^n})$
• 空间复杂度：
  • 最深的递归深度是字符串的长度n，因为每次递归调用中，我们至少处理一个字符。每层递归调用都会在栈上保存一些状态信息，因此递归栈的空间复杂度是O(n)。
  • 最坏情况下，所有划分结果的总数是$2^n$，每个结果包含的字符串总长度为n。因此，存储所有划分结果的空间复杂度是$O(n \cdot 2^n)$。

LCR087.复原IP地址

分析

针对字符串中的每个数字，通常面临两个选项。第1个选项是将当前字符拼接到当前分段数字的末尾，拼接之后的数字应该在0到255之间。第2个选项是当前字符作为一个新的分段数字的开始。需要注意的是，一个IP地址最多只有4个分段数字，并且当开始一个新的分段数字时前一个分段数字不能是空的。

如果输入的字符串的长度为n，由于逐一处理字符串中的每个字符，因此需要n步，并且每一步都面临两个可能的选项。由此可见，这个题目也适合采用回溯法解决。

class Solution {
public:
    vector<string> restoreIpAddresses(string s) {
        vector<string> res;
        helper(s, 0, "", 0, "", res);
        return res;
    }
    void helper(string s, int index, string seg, int segI, string ip, vector<string>& res){
        // 加入结果集
        if(index == s.length() && segI == 3 && isValid(seg)){
            res.push_back(ip + seg);
        }
        else if(index < s.length() && segI <= 3){
            char ch = s[index];
            // 后续字符加到当前子段
            if(isValid(seg + ch)){
                helper(s, index+1, seg+ch, segI, ip, res);
            }
            // 重新开启新子段
            if(seg.length() > 0 && segI < 3){
                helper(s, index+1, string(1, ch), segI+1, ip + seg + ".", res);
            }
        }
    }
    // 判断当前子段是否合法
    bool isValid(string seg){
        int num = stoi(seg);
        if(num <= 255 && (seg == "0" || seg[0] != '0')){
            return true;
        }
        return false;
    }
};

• 时间复杂度：$O(2^n)$
• 空间复杂度：$O(n)$

总结

本章介绍了用回溯法解决各类典型面试题。如果解决一个问题需要若干步骤，并且在每一步都面临若干选项，那么可以尝试用回溯法解决这个问题。适用回溯法的问题的一个特点是解决这个问题存在多个解，而题目往往要求列出所有的解。

应用回溯法能够解决集合的排列、组合的很多问题。仔细分析这些问题及其变种的代码就会发现最终的代码大同小异，都可以采用递归的代码实现。递归代码需要先确定递归退出的边界条件，然后逐个处理集合中的元素。对于组合类问题，每个数字都面临两个选项，即添加当前数字到组合中或不添加当前数字到组合中。对于排列类问题，一个数字如果后面有n个数字，那么面临n+1个选择，即可以将该数字和它后面的数字（也包括它自身）交换。根据这些选项做出选择之后再调用递归函数处理后面的数字。