哪个网站的域名到期直接注册表电商软文范例300字
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
加油