题目

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
回文串 是正着读和反着读都一样的字符串。

示例：

输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]

输入：s = "a"
输出：[["a"]]

解答 & 代码

解法一：动态规划预处理 + 递归回溯

递归回溯枚举所有可能的方法并进行判断：

假设当前当前搜索到字符串的第 idx 个字符，前面的 idx - 1 个字符 s[0...idx-1] 部分已经被分割为回文串且存储在 result 中。此时需要枚举下一个回文串的右边界 j，如果 s[i...j] 是回文串，就将这个回文串存入 reuslt，再递归处理分割剩余字符串。
判断 s[i...j] 是否是回文串，可以用双指针的方法，但对每个 i, j，都用双指针法判断其是否为回文子串，存在重复计算，因此可以先用动态规划进行预处理

动态规划：

动态规划数组 dp：dp[i][j] 代表 s[i...j] 是否是回文串
状态转移方程：dp[i][j] = (s[i] == s[j]) && dp[i + 1][j - 1]
- 即，s[i...j] 是回文串，当且仅当首尾字符相等(即 s[i]==s[j])，且 s[i+1...j-1] 为回文串（即 dp[i+1][j-1] == true）
初始化：当 i >= j，即 s[i...j] 为空串或长为 1 时，是回文串，此时 dp[i][j]=true

注意：状态转移的 i 要逆序遍历，j 正序遍历

因为 dp[i][j] 取决于 dp[i+1][j-1]

class Solution {
private:
  vector<vector<bool>> dp;    // 预处理的 dp 数组，dp[i][j] 代表 s[i...j] 是否是回文串
  vector<vector<string>> resultList;    // 结果数组，存储所有分割结果
  vector<string> result;                // 存储当前分割结果
  // 递归回溯分割回文串
  void backTrack(string s, int idx)
  {
      // 递归结束条件：如果遍历到字符串 s 尾部，则将当前分割结果存入结果数组，并结束递归
      if(idx == s.size())
      {
          resultList.push_back(result);
          return;
      }

      // 当前 s[0...idx-1] 部分已经被分割为回文串且存储在 result 中
      // 以 idx 为起点，向右搜索右边界 j，并判断 s[idx...j] 是否为回文串，
      // 若 s[idx...j] 为回文串，则存入 result，递归分割 s[j+1...end]
      for(int j = idx; j < s.size(); ++j)
      {
          if(dp[idx][j])    // 若 s[idx...j] 为回文串
          {
              // 选择：将 s[idx...j] 存入result
              result.push_back(s.substr(idx, j - idx + 1));
              // 递归分割 s[j+1...end]
              backTrack(s, j + 1);
              // 撤销选择：将 s[idx...j] 从 result 弹出
              result.pop_back();
          }
      }
  }
public:
  vector<vector<string>> partition(string s) {
      int len = s.size();
      // 1. 预处理，得到动态规划数组 dp，
      // 1.1 动态规划数组 dp[i][j] 代表 s[i...j] 是否是回文串
      dp.resize(len, vector<bool>(len, true));
      // 1.2 初始化：当 i >= j，即 s[i...j] 为空串或长为 1 时，是回文串，因此 dp[i][j]=true
      // 上面的语句已经默认都初始化为 true
      // 1.3 状态转移：dp[i][j] 为 true ，当且仅当首尾字符相等(即 s[i]==s[j])，
      // 且 s[i+1...j-1] 为回文串（即 dp[i+1][j-1] == true）
      for(int i = len - 1; i >= 0; --i)    // dp[i][j]取决于dp[i+1][j-1]，所以 i 倒序遍历
      {
          for(int j = i + 1; j < len; ++j)    // j 正序遍历
              dp[i][j] = (s[i] == s[j]) && dp[i + 1][j - 1];
      }

      // 2. 递归回溯
      backTrack(s, 0);
      return resultList;
  }
};

复杂度分析：设字符串 s 长为 n

时间复杂度：
- 预处理动态规划的时间复杂度
- 递归回溯的状态数，即长度为 n 的字符串的划分方案数为，而每一种合法方案最终需要 O(n) 的时间将划分方案存入结果数组
空间复杂度：
- 预处理得到动态规划数组 dp 的空间复杂度
- 递归回溯栈空间复杂度 O(n)

执行结果：

执行结果：通过

执行用时：160 ms, 在所有 C++ 提交中击败了 12.93% 的用户
内存消耗：78.1 MB, 在所有 C++ 提交中击败了 22.76% 的用户

hot 100

[中等] 131. 分割回文串

题目

解答 & 代码

解法一：动态规划预处理 + 递归回溯