Leetcode-1278.Palindrome-Partitioning-IV-CJava
目录
Leetcode-1278.Palindrome Partitioning IV [C++][Java]
[Leetcode-1278.Palindrome Partitioning IV
“Leetcode-1278.Palindrome Partitioning IV”)
[1745. 分割回文串 IV - 力扣（LeetCode）
- 分割回文串 IV - 给你一个字符串 s ，如果可以将它分割成三个 非空 回文子字符串，那么返回 true ，否则返回 false 。当一个字符串正着读和反着读是一模一样的，就称其为 回文字符串 。 示例 1：输入：s = “abcbdd"输出：true解释：“abcbdd” = “a” + “bcb” + “dd”，三个子字符串都是回文的。示例 2：输入：s = “bcbddxy"输出：false解释：s 没办法被分割成 3 个回文子字符串。 提示： * 3 <= s.length <= 2000 * s 只包含小写英文字母。
“1745. 分割回文串 IV - 力扣（LeetCode）”)
一、题目描述
Given a string
s
, return
true
if it is possible to split the string
s
into three
non-empty
palindromic substrings. Otherwise, return
false
.
A string is said to be palindrome if it the same string when reversed.
Example 1:
Input: s = "abcbdd"
Output: true
Explanation: "abcbdd" = "a" + "bcb" + "dd", and all three substrings are palindromes.Example 2:
Input: s = "bcbddxy"
Output: false
Explanation: s cannot be split into 3 palindromes.Constraints:
3 <= s.length <= 2000s consists only of lowercase English letters.
二、解题思路
- 时间复杂度：O(n^2)
- 空间复杂度：O(n^2)。
【C++】
class Solution {
public:
bool checkPartitioning(string s) {
vector<vector<bool>> isPalindrome(s.size(), vector<bool>(s.size(), true));
for (int l = s.size() - 1; l >= 0; --l) {
for (int r = l + 1; r < s.size(); ++r) {
isPalindrome[l][r] = (s[l] == s[r]) && isPalindrome[l + 1][r - 1];
}
}
for (int ml = 1; ml < s.size() - 1; ++ml) {
if (isPalindrome[0][ml - 1]) {
for (int mr = ml; mr < s.size() - 1; ++mr) {
if (isPalindrome[ml][mr] && isPalindrome[mr + 1][s.size() - 1]) {
return true;
}
}
}
}
return false;
}
};isPalindrome的优势：
- 内存局部性更优：按行从右向左填充，每次循环访问相邻内存地址，符合CPU缓存预取机制。
- 分支预测友好：无额外条件判断（如 length == 1），减少分支预测失败的开销。
- 初始化效率高：直接初始化所有元素为 true，仅需覆盖非回文区域，减少冗余操作。
【Java】
class Solution {
public boolean checkPartitioning(String s) {
boolean[][] isPalindrome = new boolean[s.length()][s.length()];
for (int l = s.length() - 1; l >= 0; --l) {
for (int r = l; r < s.length(); ++r) {
isPalindrome[l][r] = (l == r)
? true
: (s.charAt(l) == s.charAt(r)) && (l + 1 == r || isPalindrome[l + 1][r - 1]);
}
}
for (int ml = 1; ml < s.length() - 1; ++ml) {
if (isPalindrome[0][ml - 1]) {
for (int mr = ml; mr < s.length() - 1; ++mr) {
if (isPalindrome[ml][mr] && isPalindrome[mr + 1][s.length() - 1]) {
return true;
}
}
}
}
return false;
}
}