qidao123.com技术社区-IT企服评测·应用市场
标题:
LeetCode 分割回文串（回溯、dp）
[打印本页]
作者:
梦应逍遥
时间:
2025-4-18 16:32
标题:
LeetCode 分割回文串（回溯、dp）
131.分割回文串
给你一个字符串 s，请你将
s
分割成一些 子串，使每个子串都是
回文串
。返回 s 全部大概的分割方案。
示例 1：
<strong>输入：</strong>s = "aab"
<strong>输出：</strong>[["a","a","b"],["aa","b"]]
复制代码
示例 2：
<strong>输入：</strong>s = "a"
<strong>输出：</strong>[["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())
return
for 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：
<strong>输入：</strong>s = "aab"
<strong>输出：</strong>1
<strong>解释：</strong>只需一次分割就可将 <em>s </em>分割成 ["aa","b"] 这样两个回文子串。
复制代码
示例 2：
<strong>输入：</strong>s = "a"
<strong>输出：</strong>0
复制代码
示例 3：
<strong>输入：</strong>s = "ab"
<strong>输出：</strong>1
复制代码
提示：
1 <= s.length <= 2000
s 仅由小写英文字母组成
首先预处理一个 bool 数组出来使得能够快速判断字串 i-j 是否回文。定义 f 数组是前 i 个字符最少要分割几次才能全部回文，如果 g[1]
那么直接 f
= 0 就行了，否则可以枚举分割点，具体就是枚举 j ∈ [1, i) 作为分割点，如果 g[j + 1]
== true 则 f
= min(f
, 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 = '|' + s
g = [[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:
continue
if 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] = 0
else:
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：
<strong>输入：</strong>s = "abc", k = 2
<strong>输出：</strong>1
<strong>解释：</strong>你可以把字符串分割成 "ab" 和 "c"，并修改 "ab" 中的 1 个字符，将它变成回文串。
复制代码
示例 2：
<strong>输入：</strong>s = "aabbc", k = 3
<strong>输出：</strong>0
<strong>解释：</strong>你可以把字符串分割成 "aa"、"bb" 和 "c"，它们都是回文串。
复制代码
示例 3：
<strong>输入：</strong>s = "leetcode", k = 8
<strong>输出：</strong>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 = 0
while l < r:
if s[l] != s[r]:
res += 1
l, r = l + 1, r - 1
return res
f = [[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：
<strong>输入：</strong>s = "abcbdd"
<strong>输出：</strong>true
<strong>解释：</strong>"abcbdd" = "a" + "bcb" + "dd"，三个子字符串都是回文的。
复制代码
示例 2：
<strong>输入：</strong>s = "bcbddxy"
<strong>输出：</strong>false
<strong>解释：</strong>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 = '|' + s
g = [[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] = False
for i in range(1, n + 1):
if g[1][i] == False:
continue
for j in range(i + 1, n):
if g[i + 1][j] == True and g[j + 1][n] == True:
return True
return False
复制代码
加油
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
欢迎光临 qidao123.com技术社区-IT企服评测·应用市场 (https://dis.qidao123.com/)
Powered by Discuz! X3.4
