Hard

题目描述

给你一个字符串 text，你需要将其分割成 k 个子字符串（subtext1, subtext2, ..., subtextk），使得：

  • subtexti 是一个非空字符串。
  • 所有子字符串的拼接等于 text（即 subtext1 + subtext2 + ... + subtextk == text）。
  • 对于所有有效的 i（即 1 <= i <= k），都有 subtexti == subtextk - i + 1。

返回 k 的最大可能值。

示例 1：

输入：text = "ghiabcdefhelloadamhelloabcdefghi"
输出：7
解释：我们可以把字符串分割成 "(ghi)(abcdef)(hello)(adam)(hello)(abcdef)(ghi)"。

示例 2：

输入：text = "merchant"
输出：1
解释：我们可以把字符串分割成 "(merchant)"。

示例 3：

输入：text = "antaprezatepzapreanta"
输出：11
解释：我们可以把字符串分割成 "(a)(nt)(a)(pre)(za)(tep)(za)(pre)(a)(nt)(a)"。

约束条件：

  • 1 <= text.length <= 1000
  • text 只包含小写英文字母。

解题思路

这是一个关于分块回文的问题，需要我们找到最多的分块数，使得分块后形成回文结构。

核心思路：

  1. 由于要求 subtexti == subtextk - i + 1，说明分块后的字符串要满足对称性
  2. 我们可以使用贪心策略：从两端开始匹配，一旦找到相等的前缀和后缀就立即分块
  3. 这样能保证得到最多的分块数

具体算法：

  1. 使用双指针，left 指向字符串开头，right 指向字符串末尾
  2. 逐步扩展前缀和后缀，直到它们相等
  3. 找到匹配后，分块数加2（前缀和后缀各一块），然后递归处理中间部分
  4. 如果整个过程中有剩余的中间部分无法配对，则单独作为一块

为什么贪心策略正确： 如果存在更长的匹配，那么较短的匹配一定也是有效的。选择较短的匹配能够给后续留下更多的分块机会，因此贪心策略能得到最优解。

可以使用递归、迭代或动态规划来实现。这里采用简洁的递归实现。

代码实现

class Solution {
public:
    int longestDecomposition(string text) {
        int n = text.length();
        if (n == 0) return 0;
        
        // 尝试找到最短的匹配前缀和后缀
        for (int i = 1; i <= n / 2; i++) {
            string prefix = text.substr(0, i);
            string suffix = text.substr(n - i, i);
            
            if (prefix == suffix) {
                // 找到匹配，递归处理中间部分
                return 2 + longestDecomposition(text.substr(i, n - 2 * i));
            }
        }
        
        // 没有找到匹配的前缀后缀，整个字符串作为一块
        return 1;
    }
};

class Solution:
    def longestDecomposition(self, text: str) -> int:
        n = len(text)
        if n == 0:
            return 0
        
        # 尝试找到最短的匹配前缀和后缀
        for i in range(1, n // 2 + 1):
            prefix = text[:i]
            suffix = text[n-i:]
            
            if prefix == suffix:
                # 找到匹配，递归处理中间部分
                return 2 + self.longestDecomposition(text[i:n-i])
        
        # 没有找到匹配的前缀后缀，整个字符串作为一块
        return 1

public class Solution {
    public int LongestDecomposition(string text) {
        int n = text.Length;
        if (n == 0) return 0;
        
        // 尝试找到最短的匹配前缀和后缀
        for (int i = 1; i <= n / 2; i++) {
            string prefix = text.Substring(0, i);
            string suffix = text.Substring(n - i, i);
            
            if (prefix == suffix) {
                // 找到匹配，递归处理中间部分
                return 2 + LongestDecomposition(text.Substring(i, n - 2 * i));
            }
        }
        
        // 没有找到匹配的前缀后缀，整个字符串作为一块
        return 1;
    }
}

var longestDecomposition = function(text) {
    function helper(left, right) {
        if (left > right) return 0;
        if (left === right) return 1;
        
        for (let i = left, j = right; i < left + Math.floor((right - left + 1) / 2); i++, j--) {
            let leftStr = text.substring(left, i + 1);
            let rightStr = text.substring(j, right + 1);
            
            if (leftStr === rightStr) {
                return 2 + helper(i + 1, j - 1);
            }
        }
        
        return 1;
    }
    
    return helper(0, text.length - 1);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度分析
时间复杂度O(n²)，其中 n 是字符串长度。最坏情况下需要检查 n/2 种前缀后缀组合，每次字符串比较需要 O(n) 时间
空间复杂度O(n)，递归调用栈的深度最多为 n/2，每次递归可能创建新的子字符串

相关题目