[LeetCode] 每日一题 1745. 分割回文串 IV

题目链接

https://leetcode.cn/problems/palindrome-partitioning-iv

题目描述

给你一个字符串 s ，如果可以将它分割成三个 非空 回文子字符串，那么返回 true ，否则返回 false 。

当一个字符串正着读和反着读是一模一样的，就称其为 回文字符串 。

示例输入

示例 1

输入：s = "abcbdd"
输出：true
解释："abcbdd" = "a" + "bcb" + "dd"，三个子字符串都是回文的。

示例 2

输入：s = "bcbddxy"
输出：false
解释：s 没办法被分割成 3 个回文子字符串。

提示

• 3 <= s.length <= 2000

• s​​​​​​ 只包含小写英文字母。

解题思路

本题要求判断字符串 s 是否可以被分割成三个非空回文子串。相比昨天的题目，这道题更简单一些，主要考察回文判断和字符串的分割策略

我们可以分为两步解决问题：

1. 预处理回文子串
   使用动态规划 dp[left][right] 记录 s[left:right] 是否为回文：

   • 长度为 1 的子串一定是回文

   • 长度为 2 的子串如果两个字符相等，则是回文

   • 其他情况下，若 s[left] == s[right] 且 dp[left+1][right-1] 也为真，则当前子串是回文

2. 尝试分割字符串
   我们遍历 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)

总结

本题采用动态规划预处理回文子串，然后用两层循环寻找合理的分割点。与昨天的题目相比，本题无需计算最小修改次数，逻辑更清晰，主要考察回文判断和字符串分割策略

希望这篇分享能为你带来启发！如果你有任何问题或建议，欢迎在评论区留言，与我共同交流探讨。