HHot 100C++ 图解

131. 分割回文串

中等 回溯 在力扣上做

一句话套路区间 DP 预处理回文表 + 切分回溯

题目描述

给你一个字符串 s,请你将 s 分割成一些 子串,使每个子串都是 回文串 。返回 s 所有可能的分割方案。

 

示例 1:

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

示例 2:

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

 

提示:

  • 1 <= s.length <= 16
  • s 仅由小写英文字母组成

思路

时间/ O(n^2) 空间
空间

思路

把「回文切分」看成回溯:每一层枚举下一段的结束位置,是回文才递归下去。

优化

isPal[i][j] 用区间 DP 预处理(Q132 是它的「只计数」版本),把每次 O(n) 的回文判定降为 O(1)。

图解

a 0 a 1 b 2
字符串 aab(来自本仓库测试数据,下标从 0 开始)

C++17 题解

src/10_backtracking.cpp31 行
namespace lc0131 {
class Solution {
 public:
  vector<vector<string>> partition(const string& s) {
    const int n = (int)s.size();
    vector<vector<bool>> pal(n, vector<bool>(n, false));
    for (int i = n - 1; i >= 0; --i)  // 区间 DP:先算短区间
      for (int j = i; j < n; ++j)
        pal[i][j] = s[i] == s[j] && (j - i < 2 || pal[i + 1][j - 1]);
    vector<vector<string>> ans;
    vector<string> path;
    dfs(s, 0, pal, path, ans);
    return ans;
  }

 private:
  static void dfs(const string& s, int start, const vector<vector<bool>>& pal, vector<string>& path,
                  vector<vector<string>>& ans) {
    if (start == (int)s.size()) {
      ans.push_back(path);
      return;
    }
    for (int end = start; end < (int)s.size(); ++end) {
      if (!pal[start][end]) continue;  // 切出来的这段必须回文
      path.push_back(s.substr(start, end - start + 1));
      dfs(s, end + 1, pal, path, ans);
      path.pop_back();
    }
  }
};
}

单元测试

以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。

TEST q131_palindrome_partition10 行
lc0131::Solution s;
vector<vector<string>> want{{"a", "a", "b"}, {"aa", "b"}};
auto got = s.partition("aab");
sort(got.begin(), got.end());
sort(want.begin(), want.end());
CHECK_EQ(got, want);
auto single = s.partition("a");
CHECK_EQ(single, vector<vector<string>>({{"a"}}));
auto all = s.partition("aaa");
CHECK_EQ(all.size(), (size_t)4);  // a|a|a, a|aa, aa|a, aaa

↑↓ 选择↵ 打开/ 随时唤起