[Mdfs] lc131. 分割回文串(子集型枚举+选不选+选不选细节+回文串预处理优化+dp枚举顺序+好题)

1. 题目来源

链接：131. 分割回文串

必看，必刷，dfs 经典：

• [Mdfs] lc39. 组合总和(dfs+经典)
• [Mdfs] lc40. 组合总和 II(dfs+经典)
• [Mdfs] lc46. 全排列(dfs+经典)
• [Mdfs] lc47. 全排列 II(dfs搜索顺序+去重处理+知识理解+经典)
• [Mdfs] lc77. 组合(组合类型枚举+题目总结+经典)
• [Mdfs] lc78. 子集(二进制枚举+排列类型枚举+经典)
• [Mdfs] lc90. 子集 II(组合类型枚举+多重背包+去重经典)

2. 题目解析

子集型回溯的拓展题目，看看如何进行问题转换。以及代码优化，很有价值的一道题目哈。

思路：选不选

• 针对 “aab” 来看，实际上就是枚举下每个分隔符到底要不要进行分割。
• 这样的话，就枚举出了所有的分割方案，然后再进行回文串判断即可。
• 那么问题就转变成了 [Mdfs] lc78. 子集(二进制枚举+排列类型枚举+经典) 中的，选不选问题。
• 同样的，有两种 dfs 做法：
  • 每个分割串，选不选 的做法。
  • for 循环枚举子串的结束位置。
• 值得注意的是，对于 选不选 问题而言，是有可能出现空集的，即一路都走到不选的情况，导致对字符串的划分出现问题。
• 这里就有一个技巧了，我们是优先枚举 不选 的。那么只需要加入一个判断，保证最后一位必须要选即可，即保证字符串一定能在末尾被划分即可。
• 具体看代码，简单易懂。

---

思路：for 循环枚举划分位置

• 这个比较简单易理解，dfs 枚举划分子串的结束位置即可。

---

优化思路：预处理回文串

• 这个是比较经典的一个预处理问题。
• 记 f[i][j] 为 [i, j] 下标的子字符串，是否为回文串。
• 那么 f[i][j] = (f[i+1][j-1]) && s[i]==s[j] 进行状态转移。
• 观察这个状态转移，这个 j 状态会依赖 j-1 状态。即 j 是依赖前一个状态的。这里就需要注意一下枚举顺序了，要求 j 要能提前被算出。故，j 要先进行枚举。
• 这个枚举顺序还是很关键的哈，可以想一想之前 f[i][j]=f[i-1][j]+x 这样的枚举，为啥是先 i 再 j。而现在 f[i][j]=f[i+1][j-1] 就是先 j 再 i 了哈。

---

时间复杂度：$O(n\ast 2^n)$

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

---

选不选、简单判断 回文串：

class Solution {
public:vector<vector<string>> all;vector<string> path; void dfs(string s, int last, int u) {if (u == s.size()) {all.push_back(path);return ;}// 这个很关键哈。这个 u=n-1 时意味着一定会选，if (u < s.size() - 1) dfs(s, last, u + 1);path.push_back(s.substr(last, u - last + 1));dfs(s, u + 1, u + 1);path.pop_back();}vector<vector<string>> partition(string s) {int n = s.size();dfs(s, 0, 0);vector<vector<string>> res;for (auto& v : all) {bool flag = true;for (auto& t : v) {int n = t.size();for (int l = 0, r = n - 1; l < r; l ++ , r -- ) {if (t[l] != t[r]) {flag = false;break;}}if (!flag) break;}if (flag) res.push_back(v);}return res;}
};

---

for 循环枚举划分位置

class Solution {
public:vector<vector<string>> all;vector<string> path;void dfs(string s, int u) {if (u == s.size()) {all.push_back(path);return ;}for (int i = u; i < s.size(); i ++ ) {path.push_back(s.substr(u, i - u + 1));dfs(s, i + 1);path.pop_back();}}vector<vector<string>> partition(string s) {int n = s.size();dfs(s, 0);vector<vector<string>> res;for (auto& v : all) {bool flag = true;for (auto& t : v) {int n = t.size();for (int l = 0, r = n - 1; l < r; l ++ , r -- ) {if (t[l] != t[r]) {flag = false;break;}}if (!flag) break;}if (flag) res.push_back(v);}return res;}
};

---

回文串判断优化：

class Solution {
public:vector<vector<bool>> f;vector<vector<string>> res;vector<string> path;void dfs(string s, int u) {if (u == s.size()) {res.push_back(path);return ;}for (int i = u; i < s.size(); i ++ ) {if (f[u][i]) {path.push_back(s.substr(u, i - u + 1));dfs(s, i + 1);path.pop_back();}}}vector<vector<string>> partition(string s) {int n = s.size();f = vector<vector<bool>>(n, vector<bool>(n));for (int j = 0; j < n; j ++ )for (int i = 0; i <= j; i ++ ) {if (i == j) f[i][j] = true;else if (s[i] == s[j]) {// 只有两个字符，或者 f[i+1][j-1] 是回文的，则状态转移到 f[i][j]if (i + 1 > j - 1 || f[i + 1][j - 1]) f[i][j] = true;}}dfs(s, 0);return res;}
};