每日一题时间:
2020-03-08
题目链接: 132. 分割回文串 II 官方题解链接: 分割回文串 II
给你一个字符串 s
,请你将 s
分割成一些子串,使每个子串都是回文。
返回符合要求的 最少分割次数 。
示例 1:
输入:s = "aab"
输出:1
解释:只需一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。
示例 2:
输入:s = "a"
输出:0
示例 3:
输入:s = "ab"
输出:1
提示:
1 <= s.length <= 2000
s
仅由小写英文字母组成这道题与 131. 分割回文串 很相似首先采用其方法进行解题
该部分需要注意的是 对于返回结果是 res - 1
class Solution {
private:
vector<vector<int>> dp;
int minRes = INT_MAX;
int cur = 0;
int isPalindrome(string &s, int left, int right) {
if (left >= right) dp[left][right] = 1;
if (dp[left][right] == 0) {
dp[left][right] = s[left] != s[right] ? -1 : isPalindrome(s, left + 1, right - 1);
}
return dp[left][right];
}
void dfs(string &s, int start) {
if (start >= s.size()) {
minRes = min(cur, minRes);
}
for (int end = start; end < s.size(); ++end) {
if(isPalindrome(s, start, end) == 1) {
++cur;
dfs(s, end + 1);
--cur;
}
}
}
public:
int minCut(string s) {
dp.assign(s.size(), vector<int>(s.size()));
dfs(s, 0);
return minRes - 1;
}
};
O(N 2^N)
O(N N)
设 g(i, j) 表示 si..j 是否为回文串,那么有状态转移方程:
`$$
g(i, j) = \begin{cases}
\texttt{True}, & \quad i \geq j \
g(i+1,j-1) \wedge (si=sj), & \quad \text{otherwise}
\end{cases}
$$`
其中 \wedge 表示逻辑与运算,即 si..j 为回文串,当且仅当其为空串(i>j),其长度为 1(i=j),或者首尾字符相同且 si+1..j-1 为回文串。
这里的动态规划扫描回文串的方式需要注意一下.
class Solution {
public:
int minCut(string s) {
int n = s.size();
vector<vector<int>> g(n, vector<int>(n, true));
for (int i = n - 1; i >= 0; --i) {
for (int j = i + 1; j < n; ++j) {
g[i][j] = (s[i] == s[j]) && g[i + 1][j - 1];
}
}
vector<int> f(n, INT_MAX);
for (int i = 0; i < n; ++i) {
if (g[0][i]) {
f[i] = 0;
} else {
for (int j = 0; j < i; ++j) {
if (g[j + 1][i]) {
f[i] = min(f[i], f[j] + 1);
}
}
}
}
return f[n - 1];
}
};
O(N^2)
O(N^2)
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。