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

131.分割回文串

给你一个字符串 s，请你将 s 分割成一些 子串，使每个子串都是 回文串 。返回 s 全部大概的分割方案。
示例 1：

1. <strong>输入：</strong>s = "aab"
2. <strong>输出：</strong>[["a","a","b"],["aa","b"]]

复制代码

示例 2：

1. <strong>输入：</strong>s = "a"
2. <strong>输出：</strong>[["a"]]

复制代码

提示：

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

在求具体的方案数时一样寻常用深搜来解决，尤其是 n 最多只有 16 时，实在已经提示了用 dfs 来写
通过枚举起点和尽头来不绝回溯搜索
代码

c++

1. class Solution {
2. public:
3.     vector<vector<string>> partition(string s) {
4.         int n = s.size();
5.         s = '|' + s;
6.         vector<string> path;
7.         vector<vector<string>> ans;
8.         auto check = [&](string s) -> bool{
9.             string s1 = s, s2 = s;
10.             reverse(s2.begin(), s2.end());
11.             return s1 == s2;
12.         };
13.         auto dfs = [&](auto &&self, int u) -> void{
14.             if(u > n){
15.                 ans.push_back(path);
16.                 return;
17.             }
18.             for(int i = u;i <= n;i ++){
19.                 string ss = s.substr(u, i - u + 1);
20.                 if(check(ss)){
21.                     path.push_back(ss);
22.                     self(self, i + 1);
23.                     path.pop_back();
24.                 }
25.             }
26.         };
27.         dfs(dfs, 1);
28.         return ans;
29.     }
30. };

复制代码

py

1. class Solution:
2.     def partition(self, s: str) -> List[List[str]]:
3.         n = len(s)
4.         ans = []
5.         path = []
6.         def check(s) -> bool:
7.             return s == s[::-1]
8.         def dfs(x) -> None:
9.             if x == n:
10.                 ans.append(path.copy())
11.                 return
12.             for i in range(x, n):
13.                 if check(s[x : i + 1]):
14.                     path.append(s[x : i + 1])
15.                     dfs(i + 1)
16.                     path.pop()
17.         dfs(0)
18.         return ans
19.         

复制代码

132.分割回文串 II

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文串。
返回符合要求的 最少分割次数 。
示例 1：

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

复制代码

示例 2：

1. <strong>输入：</strong>s = "a"
2. <strong>输出：</strong>0

复制代码

示例 3：

1. <strong>输入：</strong>s = "ab"
2. <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)
超时代码

1. class Solution {
2. public:
3.     int minCut(string s) {
4.         int n = s.size();
5.         s = '|' + s;
6.         vector<vector<bool>> g(n + 1, vector<bool>(n + 1, true));
7.         vector<int> f(n + 1, INT_MAX);
8.         for(int i = 1;i <= n;i ++){
9.             for(int j = i;j <= n;j ++){
10.                 if(i == j) continue;
11.                 string s1 = s.substr(i, j - i + 1), s2 = s1;
12.                 reverse(s2.begin(), s2.end());
13.                 if(s1 != s2) g[i][j] = false;
14.             }
15.         }
16.         for(int i = 1;i <= n;i ++){
17.             if(g[1][i]) f[i] = 0;
18.             else{
19.                 for(int j = 1;j < i;j ++) if(g[j + 1][i]){
20.                     f[i] = min(f[i], f[j] + 1);
21.                 }
22.             }
23.         }
24.         return f[n];
25.     }
26. };

复制代码

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

1. from math import *
3. class Solution:
4.     def minCut(self, s: str) -> int:
5.         n = len(s)
6.         s = '|' + s
7.         g = [[True] * (n + 1) for _ in range(n + 1)]
8.         f = [inf] * (n + 1)
9.         for i in range(1, n + 1):
10.             for j in range(i, n + 1):
11.                 if i == j:
12.                     continue
13.                 if s[i:j+1] != s[i:j+1][::-1]:
14.                     g[i][j] = False
15.                 # print(f"{i}-{j}:{g[i][j]}")
16.         for i in range(1, n + 1):
17.             if g[1][i]:
18.                 f[i] = 0
19.             else:
20.                 for j in range(1, i):
21.                     if g[j+1][i]:
22.                         f[i] = min(f[i], f[j] + 1)
23.         return f[n]

复制代码

1278.分割回文串 III 

给你一个由小写字母组成的字符串 s，和一个整数 k。
请你按下面的要求分割字符串：

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

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

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

复制代码

示例 2：

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

复制代码

示例 3：

1. <strong>输入：</strong>s = "leetcode", k = 8
2. <strong>输出：</strong>0

复制代码

提示：

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

递推，这个问题需要考虑一个二维 f 数组 ：使前 i 项 分割成 k 个回文字符串需要修改的最小次数
用一个函数来调用：一个字符串需要修改多少字符酿成回文串。初始状态 f[0][0] 就是 0 ，枚举递推即可
代码

c++

1. class Solution {
2. public:
3.     int palindromePartition(string s, int k) {
4.         int n = s.size();
5.         if(n == k) return 0;
6.         vector<vector<int>> f(n + 1, vector<int>(k + 1, 0x3f3f3f3f));
7.         f[0][0] = 0;
8.         auto get = [&](string s, int ist, int ed) -> int{
9.             int l = ist, r = ed, res = 0;
10.             for(;l < r;l ++, r --) if(s[l] != s[r]){
11.                 res ++;
12.             }
13.             return res;
14.         };
15.         for(int i = 1;i <= n;i ++){
16.             for(int j = 1;j <= min(i, k);j ++){
17.                 if(j == 1) f[i][j] = get(s, 0, i - 1);
18.                 else{
19.                     for(int z = j - 1;z < i;z ++){
20.                         f[i][j] = min(f[i][j], f[z][j - 1] + get(s, z, i - 1));
21.                     }
22.                 }
23.             }
24.         }
25.         return f[n][k];
26.     }
27. };

复制代码

py

1. class Solution:
2.     def palindromePartition(self, s: str, k: int) -> int:
3.         n = len(s)
4.         def get(s, l, r):
5.             res = 0
6.             while l < r:
7.                 if s[l] != s[r]:
8.                     res += 1
9.                 l, r = l + 1, r - 1
10.             return res
11.         f = [[inf] * (k + 1) for _ in range(n + 1)]
12.         for i in range(1, n + 1):
13.             for j in range(1, min(i, k) + 1):
14.                 if j == 1:
15.                     f[i][j] = get(s, 0, i - 1)
16.                 else:
17.                     for z in range(j - 1, i):
18.                         f[i][j] = min(f[i][j], f[z][j - 1] + get(s, z, i - 1))
19.         return f[n][k]

复制代码

1745.分割回文串 IV

给你一个字符串 s ，如果可以将它分割成三个 非空 回文子字符串，那么返回 true ，否则返回 false 。
当一个字符串正着读和反着读是千篇一律的，就称其为 回文字符串 。
示例 1：

1. <strong>输入：</strong>s = "abcbdd"
2. <strong>输出：</strong>true
3. <strong>解释：</strong>"abcbdd" = "a" + "bcb" + "dd"，三个子字符串都是回文的。

复制代码

示例 2：

1. <strong>输入：</strong>s = "bcbddxy"
2. <strong>输出：</strong>false
3. <strong>解释：</strong>s 没办法被分割成 3 个回文子字符串

复制代码

提示：

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

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

py

1. from math import *
3. class Solution:
4.     def checkPartitioning(self, s: str) -> bool:
5.         n = len(s)
6.         s = '|' + s
7.         g = [[True] * (n + 1) for _ in range(n + 1)]
8.         for i in range(1, n + 1):
9.             for j in range(i + 1, n + 1):
10.                 if s[i:j+1] != s[i:j+1][::-1]:
11.                     g[i][j] = False
12.         for i in range(1, n + 1):
13.             if g[1][i] == False:
14.                 continue
15.             for j in range(i + 1, n):
16.                 if g[i + 1][j] == True and g[j + 1][n] == True:
17.                     return True
18.         return False

复制代码

加油

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。