LeetCode 分割回文串（回溯、dp）

131.分割回文串

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

示例 1：

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

示例 2：

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

提示：

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

在求具体的方案数时一般用深搜来解决，尤其是 n 最多只有 16 时，其实已经提醒了用 dfs 来写

通过枚举起点和终点来不断回溯搜索

代码

c++

class Solution {
public:vector<vector<string>> partition(string s) {int n = s.size();s = '|' + s;vector<string> path;vector<vector<string>> ans;auto check = [&](string s) -> bool{string s1 = s, s2 = s;reverse(s2.begin(), s2.end());return s1 == s2;};auto dfs = [&](auto &&self, int u) -> void{if(u > n){ans.push_back(path);return;}for(int i = u;i <= n;i ++){string ss = s.substr(u, i - u + 1);if(check(ss)){path.push_back(ss);self(self, i + 1);path.pop_back();}}};dfs(dfs, 1);return ans;}
};

py

class Solution:def partition(self, s: str) -> List[List[str]]:n = len(s)ans = []path = []def check(s) -> bool:return s == s[::-1]def dfs(x) -> None:if x == n:ans.append(path.copy())returnfor i in range(x, n):if check(s[x : i + 1]):path.append(s[x : i + 1])dfs(i + 1)path.pop()dfs(0)return ans

132.分割回文串 II

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文串。

返回符合要求的 最少分割次数 。

示例 1：

输入：s = "aab"
输出：1
解释：只需一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。

示例 2：

输入：s = "a"
输出：0

示例 3：

输入：s = "ab"
输出：1

提示：

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

首先预处理一个 bool 数组出来使得能够快速判断字串 i-j 是否回文。定义 f 数组是前 i 个字符最少要分割几次才能全部回文，如果 g[1][i] 那么直接 f[i] = 0 就行了，否则可以枚举分割点，具体就是枚举 j ∈ [1, i) 作为分割点，如果 g[j + 1][i] == true 则 f[i] = min(f[i], f[j] + 1)

超时代码

class Solution {
public:int minCut(string s) {int n = s.size();s = '|' + s;vector<vector<bool>> g(n + 1, vector<bool>(n + 1, true));vector<int> f(n + 1, INT_MAX);for(int i = 1;i <= n;i ++){for(int j = i;j <= n;j ++){if(i == j) continue;string s1 = s.substr(i, j - i + 1), s2 = s1;reverse(s2.begin(), s2.end());if(s1 != s2) g[i][j] = false;}}for(int i = 1;i <= n;i ++){if(g[1][i]) f[i] = 0;else{for(int j = 1;j < i;j ++) if(g[j + 1][i]){f[i] = min(f[i], f[j] + 1);}}}return f[n];}
};

在预处理部分的 reverse 和 substr 部分会导致超时，那么这时候只需要换成 py 的代码，就可以水过这个数据

代码

from math import *class Solution:def minCut(self, s: str) -> int:n = len(s)s = '|' + sg = [[True] * (n + 1) for _ in range(n + 1)]f = [inf] * (n + 1) for i in range(1, n + 1):for j in range(i, n + 1):if i == j:continueif s[i:j+1] != s[i:j+1][::-1]:g[i][j] = False# print(f"{i}-{j}:{g[i][j]}")for i in range(1, n + 1):if g[1][i]:f[i] = 0else:for j in range(1, i):if g[j+1][i]:f[i] = min(f[i], f[j] + 1)return f[n]

1278.分割回文串 III 

给你一个由小写字母组成的字符串 s，和一个整数 k。

请你按下面的要求分割字符串：

• 首先，你可以将 s 中的部分字符修改为其他的小写英文字母。
• 接着，你需要把 s 分割成 k 个非空且不相交的子串，并且每个子串都是回文串。

请返回以这种方式分割字符串所需修改的最少字符数。

示例 1：

输入：s = "abc", k = 2
输出：1
解释：你可以把字符串分割成 "ab" 和 "c"，并修改 "ab" 中的 1 个字符，将它变成回文串。

示例 2：

输入：s = "aabbc", k = 3
输出：0
解释：你可以把字符串分割成 "aa"、"bb" 和 "c"，它们都是回文串。

示例 3：

输入：s = "leetcode", k = 8
输出：0

提示：

• 1 <= k <= s.length <= 100
• s 中只含有小写英文字母。

递推，这个问题需要考虑一个二维 f 数组 ：使前 i 项 分割成 k 个回文字符串需要修改的最小次数

用一个函数来调用：一个字符串需要修改多少字符变成回文串。初始状态 f[0][0] 就是 0 ，枚举递推即可

代码

c++

class Solution {
public:int palindromePartition(string s, int k) {int n = s.size();if(n == k) return 0;vector<vector<int>> f(n + 1, vector<int>(k + 1, 0x3f3f3f3f));f[0][0] = 0;auto get = [&](string s, int ist, int ed) -> int{int l = ist, r = ed, res = 0;for(;l < r;l ++, r --) if(s[l] != s[r]){res ++;}return res;};for(int i = 1;i <= n;i ++){for(int j = 1;j <= min(i, k);j ++){if(j == 1) f[i][j] = get(s, 0, i - 1);else{for(int z = j - 1;z < i;z ++){f[i][j] = min(f[i][j], f[z][j - 1] + get(s, z, i - 1));}}}}return f[n][k];}
};

py

class Solution:def palindromePartition(self, s: str, k: int) -> int:n = len(s)def get(s, l, r):res = 0while l < r:if s[l] != s[r]:res += 1l, r = l + 1, r - 1return resf = [[inf] * (k + 1) for _ in range(n + 1)]for i in range(1, n + 1):for j in range(1, min(i, k) + 1):if j == 1:f[i][j] = get(s, 0, i - 1)else:for z in range(j - 1, i):f[i][j] = min(f[i][j], f[z][j - 1] + get(s, z, i - 1))return f[n][k]

1745.分割回文串 IV

给你一个字符串 s ，如果可以将它分割成三个 非空 回文子字符串，那么返回 true ，否则返回 false 。

当一个字符串正着读和反着读是一模一样的，就称其为 回文字符串 。

示例 1：

输入：s = "abcbdd"
输出：true
解释："abcbdd" = "a" + "bcb" + "dd"，三个子字符串都是回文的。

示例 2：

输入：s = "bcbddxy"
输出：false
解释：s 没办法被分割成 3 个回文子字符串

提示：

• 3 <= s.length <= 2000
• s​​​​​​ 只包含小写英文字母。

这个问题跟 || 本质是一样的，只是有一个有一个类似三数之和的枚举技巧，先枚举第一段，然后枚举第二段，剩下的就是第三段，预处理之后 O（1）查询即可

代码

py

from math import *class Solution:def checkPartitioning(self, s: str) -> bool:n = len(s)s = '|' + sg = [[True] * (n + 1) for _ in range(n + 1)]for i in range(1, n + 1):for j in range(i + 1, n + 1):if s[i:j+1] != s[i:j+1][::-1]:g[i][j] = Falsefor i in range(1, n + 1):if g[1][i] == False:continuefor j in range(i + 1, n):if g[i + 1][j] == True and g[j + 1][n] == True:return Truereturn False

加油