[LeetCode] 每日一题 1745. 分割回文串 IV
题目链接
题目描述
给你一个字符串 s
,如果可以将它分割成三个 非空 回文子字符串,那么返回 true
,否则返回 false
。
当一个字符串正着读和反着读是一模一样的,就称其为 回文字符串 。
示例输入
示例 1
输入:s = "abcbdd"
输出:true
解释:"abcbdd" = "a" + "bcb" + "dd",三个子字符串都是回文的。
示例 2
输入:s = "bcbddxy"
输出:false
解释:s 没办法被分割成 3 个回文子字符串。
提示
3 <= s.length <= 2000
s
只包含小写英文字母。
解题思路
本题要求判断字符串 s
是否可以被分割成三个非空回文子串。相比昨天的题目,这道题更简单一些,主要考察回文判断和字符串的分割策略
我们可以分为两步解决问题:
预处理回文子串
使用动态规划dp[left][right]
记录s[left:right]
是否为回文:长度为
1
的子串一定是回文长度为
2
的子串如果两个字符相等,则是回文其他情况下,若
s[left] == s[right]
且dp[left+1][right-1]
也为真,则当前子串是回文
尝试分割字符串
我们遍历i
和j
,尝试将s
划分为[0, i-1]
、[i, j]
和[j+1, n-1]
三部分,并判断它们是否都是回文:第一层循环
i
,确保[0, i-1]
是回文第二层循环
j
,确保[i, j]
和[j+1, n-1]
都是回文
如果找到符合条件的 i
和 j
,返回 true
,否则返回 false
代码实现
class Solution {
public boolean checkPartitioning(String s) {
int n = s.length();
boolean[][] dp = new boolean[n][n];
// 预处理回文子串
for (int len = 1; len <= n; len++) {
for (int left = 0; left <= n - len; left++) {
int right = left + len - 1;
if (len == 1) {
dp[left][right] = true;
} else if (len == 2) {
dp[left][right] = s.charAt(left) == s.charAt(right);
} else {
dp[left][right] = s.charAt(left) == s.charAt(right) && dp[left + 1][right - 1];
}
}
}
// 遍历分割点
for (int i = 1; i < n - 1; i++) {
if (!dp[0][i - 1]) continue;
for (int j = i; j < n - 1; j++) {
if (dp[i][j] && dp[j + 1][n - 1]) {
return true;
}
}
}
return false;
}
}
复杂度分析
时间复杂度:
预处理
dp
数组需要 O(n^2)遍历
i
和j
进行分割需要 O(n^2)因此,总体时间复杂度为 O(n^2 + n^2) = O(n^2)
空间复杂度:
dp
数组占用 O(n^2)其他变量占用 O(1)
总体空间复杂度为 O(n^2)
总结
本题采用动态规划预处理回文子串,然后用两层循环寻找合理的分割点。与昨天的题目相比,本题无需计算最小修改次数,逻辑更清晰,主要考察回文判断和字符串分割策略
希望这篇分享能为你带来启发!如果你有任何问题或建议,欢迎在评论区留言,与我共同交流探讨。