文章

[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. 尝试分割字符串
    我们遍历 ij,尝试将 s 划分为 [0, i-1][i, j][j+1, n-1] 三部分,并判断它们是否都是回文:

    • 第一层循环 i,确保 [0, i-1] 是回文

    • 第二层循环 j,确保 [i, j][j+1, n-1] 都是回文

如果找到符合条件的 ij,返回 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)

    • 遍历 ij 进行分割需要 O(n^2)

    • 因此,总体时间复杂度为 O(n^2 + n^2) = O(n^2)

  • 空间复杂度

    • dp 数组占用 O(n^2)

    • 其他变量占用 O(1)

    • 总体空间复杂度为 O(n^2)

总结

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

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

License:  CC BY 4.0