各位题友大家好！今天是 @负雪明烛 坚持日更的第 42 天。今天力扣上的每日一题是「131. 分割回文串」。

解题思路

题意：把输入字符串分割成回文子串的所有可能的结果。

回溯法

看到题目要求「所有可能的结果」，而不是「结果的个数」，一般情况下，我们就知道需要暴力搜索所有的可行解了，可以用「回溯法」。

「回溯法」实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。

回溯法是一种算法思想，而递归是一种编程技巧，回溯法可以用递归来实现。

回溯法的整体思路是：回溯法是搜索每一条路，每次 backtrack 是对具体的一条路径而言的。对当前搜索路径下的的未探索区域进行搜索，则可能有两种情况：

当前未搜索区域满足结束条件，则保存当前路径并退出当前搜索；
2. 当前未搜索区域需要继续搜索，则遍历当前所有可能的选择：如果该选择符合要求，则把当前选择加入当前的搜索路径中，并继续搜索新的未探索区域。

上面说的未搜索区域是指搜索某条路径时的未搜索区域，并不是全局的未搜索区域。

回溯法搜所有可行解的模板一般是这样的（今天刚构思的，欢迎拍砖）：

res = []
path = []
def backtrack(未探索区域, res, path):
    if 未探索区域满足结束条件:
        res.add(path) # 深度拷贝
        return
    for 选择 in 未探索区域当前可能的选择:
        if 当前选择符合要求:
            path.add(当前选择)
            backtrack(新的未探索区域, res, path)
            path.pop()

定义的 backtrack 的含义是：未探索区域中到达结束条件的所有可能路径，path 变量是保存的是一条路径，res 变量保存的是所有搜索到的路径。所以当「未探索区域满足结束条件」时，需要把 path 放到结果 res 中。path.pop() 是啥意思呢？它是语言实现上的一个要求，即我们从始至终只用了一个变量 path，所以当对path 增加一个选择并 backtrack 之后，需要清除当前的选择，防止影响其他路径的搜索。

本题需要我们把字符串分成一系列的回文子串，按照模板，我们的思路应该是这样的：

未探索区域：剩余的未搜索的字符串 s；
2. 结束条件：s 为空；
3. 未探索区域当前可能的选择：每次选择可以选取 s 的 1 - length 个字符，cur = s[0…i]；
4. 当前选择符合要求：cur 是回文字符串 isPalindrome(cur)；
5. 新的未探索区域：s 去除掉 cur 的剩余字符串，s[i + 1…N]。

代码

下面分享了两种解法，分别对应了每次复制 path 和不复制 path 的解法。这里是一个容易出错的细节。

Python 解法在每次搜索位置区域的时候，使用的是产生一个新数组 path + [s[:i]] ，这样好处是方便：不同的路径使用的是不同的 path，因此不需要 path.pop() 操作；而且 res.append(path) 的时候不用深度拷贝一遍 path。

C++ 解法使用的是和我上面分析的一样的所有路径共享 path 的实现，需要对 path 进行 push 和 pop 操作，当把 path 放入 res 中时，需要深度拷贝，而 vector 的 push_back() 函数，本身就是深度拷贝。

class Solution(object):
  def partition(self, s):
      """
      :type s: str
      :rtype: List[List[str]]
      """
      self.isPalindrome = lambda s : s == s[::-1]
      res = []
      self.helper(s, res, [])
      return res
  def helper(self, s, res, path):
      if not s:
          res.append(path)
          return
      for i in range(1, len(s) + 1): #注意起始和结束位置
          if self.isPalindrome(s[:i]):
              self.helper(s[i:], res, path + [s[:i]])

class Solution {
public:
    vector<vector<string>> partition(string s) {
        vector<vector<string>> res;
        helper(s, res, {});
        return res;
    }
    void helper(string s, vector<vector<string>>& res, vector<string> path) {
        if (s.size() == 0) {
            res.push_back(path);
            return;
        }
        for (int i = 1; i <= s.size(); i++) {
            string pre = s.substr(0, i);
            if (isPalindrome(pre)) {
                path.push_back(pre);
                helper(s.substr(i), res, path);
                path.pop_back();
            }
        }
    }
    bool isPalindrome(string s) {
        if (s.size() == 0) return true;
        int start = 0, end = s.size() - 1;
        while (start <= end) {
            if (s[start] != s[end])
                return false;
            start ++;
            end --;
        }
        return true;
    }
};

时间复杂度：$O(N * 2 ^ N)$，因为总共有 $O(2^N)$ 种分割方法，每次分割都要判断是否回文需要 $O(N)$ 的时间复杂度。
空间复杂度：$O(2 ^ N)$，返回结果最多有 $O(2 ^ N)$ 种划分方法。

刷题心得

回溯法是个比较经典的方法，通常可以用递归来实现。
- 我最喜欢刷回溯法的题目了，因为模板是通用的。

参考资料：
1. 力扣官方题解：分割回文串
2. liweiwei1419：回溯算法、优化（使用动态规划预处理数组）
3. 笨猪爆破组
4. https://www.cnblogs.com/fanguangdexiaoyuer/p/11224426.html
5. 【LeetCode】代码模板，刷题必会

OK，以上就是 @负雪明烛写的今天题解的全部内容了，如果你觉得有帮助的话，求赞、求关注、求收藏。如果有疑问的话，请在下面评论，我会及时解答。

关注我，你将不会错过我的精彩动画题解、面试题分享、组队刷题活动，进入主页 @负雪明烛右侧有刷题组织，从此刷题不再孤单。

祝大家 AC 多多，Offer 多多！我们明天再见！

算法每日一题题解

【每日一题】131. 分割回文串

解题思路

回溯法

代码

刷题心得