131. 分割回文串
一句话套路区间 DP 预处理回文表 + 切分回溯
题目描述
给你一个字符串 s,请你将 s 分割成一些 子串,使每个子串都是 回文串 。返回 s 所有可能的分割方案。
示例 1:
输入:s = "aab" 输出:[["a","a","b"],["aa","b"]]
示例 2:
输入:s = "a" 输出:[["a"]]
提示:
1 <= s.length <= 16s仅由小写英文字母组成
思路
时间/
O(n^2) 空间空间
思路
把「回文切分」看成回溯:每一层枚举下一段的结束位置,是回文才递归下去。
优化
isPal[i][j] 用区间 DP 预处理(Q132 是它的「只计数」版本),把每次 O(n) 的回文判定降为 O(1)。
图解
字符串
aab(来自本仓库测试数据,下标从 0 开始)C++17 题解
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();
}
}
};
}
单元测试
以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。
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