LeetCode 1147. 段式回文

约 6 分钟
文章信息 6 个分类 6 个标签
分类
LeetCode CodeTop 困难 未解决 1-2 字节
标签
字符串 动态规划 双指针 贪心 哈希函数 滚动哈希

题目描述

✅ 1147. 段式回文

image-20260929074823328

image-20260929074823572

题意分析

将整个字符串按原顺序切成若干个非空连续片段，要求第一段与最后一段完全相同，第二段与倒数第二段完全相同，依次向内对应，求最多能切成多少段。

相同片段比较的是原内容，不需要反转字符。所有字符都必须被某一段覆盖，段与段之间不能重叠；如果段数为奇数，中间一段只需与自身对应，可以是任意内容。

解法：双指针分段匹配

核心思路

[!blue]

用闭区间 [left, right] 表示还没有分段的中间部分。从长度一开始，依次比较它的等长前缀和后缀，找到第一对相等片段就立即取出，答案加二，再处理剩余中间区间。候选长度最多为剩余长度的一半，保证这两段不重叠。

为什么选择最短匹配不会妨碍最多分段？设最短相等前后缀为 P，某个最优分法的外层片段为 A。存在可匹配两段时，最优分法至少能有两段，因此确实存在这样的一对外层。A 不可能比 P 短；若一样长，贪心已经与最优外层相同。

假设 A 更长，因为它既位于原区间开头又位于结尾，P 同时是 A 的前缀和后缀。如果这两份 P 在 A 中重叠，重叠长度为 2 * |P| - |A|，它是正数且短于 P。重叠迫使 P 的这一段前后缀也相同，于是原区间存在更短匹配，和 P 最短矛盾。

所以这两份 P 必须不重叠，A 可以进一步拆成 P、可选中间块、P。把最优解左右两份 A 同时这样细分，仍满足片段对称，却得到更多段，又与最优性矛盾。因此最优外层可以直接取最短匹配，剥离后对中间部分重复相同选择即可。

如果所有不重叠的等长前后缀都不相同，剩余区间不可能再拆出一对外层段，只能整体作为中心一段。若两端刚好被全部剥离，剩余区间为空，就无需再加中心段。比较直接使用下标，不创建候选子串。

解题步骤

  1. 初始化左右边界和已确定段数。
  2. 在剩余长度一半的范围内，从短到长逐字符比较等长前后缀。
  3. 第一对匹配出现后，答案加二，两端各缩进匹配长度，立即开始下一轮。
  4. 本轮完全没有匹配时，返回已确定段数加一，把剩余内容视为中心。
  5. 若区间被配对剥离为空，则返回当前段数。

代码实现

class Solution {
    public int longestDecomposition(String text) {
        int left = 0;
        int right = text.length() - 1;
        int answer = 0;

        while (left <= right) {
            boolean paired = false;
            // 两段必须不重叠，候选长度最多为剩余长度的一半。
            int maxLen = (right - left + 1) / 2;

            for (int len = 1; len <= maxLen; len++) {
                // 第一次相等就是最短匹配，取这一对后立即向内收缩。
                if (equal(text, left, right - len + 1, len)) {
                    answer += 2;
                    left += len;
                    right -= len;
                    paired = true;
                    break;
                }
            }

            // 没有可配对的前后缀，剩余整体作为中心一段。
            if (!paired) {
                return answer + 1;
            }
        }

        return answer;
    }

    private boolean equal(String text, int a, int b, int len) {
        for (int offset = 0; offset < len; offset++) {
            if (text.charAt(a + offset) != text.charAt(b + offset)) {
                return false;
            }
        }

        return true;
    }
}

func longestDecomposition(text string) int {
    left, right := 0, len(text)-1
    answer := 0

    for left <= right {
        paired := false
        // 两段必须不重叠，候选长度最多为剩余长度的一半。
        maxLen := (right - left + 1) / 2
        for length := 1; length <= maxLen; length++ {
            // 第一次相等就是最短匹配，取这一对后立即向内收缩。
            if equalChunk(text, left, right-length+1, length) {
                answer += 2
                left += length
                right -= length
                paired = true
                break
            }
        }
        // 没有可配对的前后缀，剩余整体作为中心一段。
        if !paired {
            return answer + 1
        }
    }
    return answer
}

func equalChunk(text string, a, b, length int) bool {
    for offset := 0; offset < length; offset++ {
        if text[a+offset] != text[b+offset] {
            return false
        }
    }
    return true
}

复杂度分析

  • 时间复杂度：$O(n^2)$。一轮若尝试到长度 t，比较上界为 $1 + 2 + \cdots + t$；成功轮会移除 2t 个字符，最后失败轮至多扫描剩余长度的一半，所有轮累计仍不超过平方级。
  • 空间复杂度：$O(1)$，只用边界和计数，候选片段按原串下标比较，没有递归栈或子串缓冲。

关键点总结

[!green]

  • 最短相等前后缀可以直接作为最优外层，选择依据是可进一步细分的交换论证。
  • 找到第一对匹配就收缩，继续扩大外层只会错失更细的划分。
  • 没有可配对外层时，剩余内容只能贡献一段；区间为空则不贡献中心段。
  • 左右候选必须等长、不重叠，并保持原字符顺序。

易错点总结

[!yellow]

  • 反转右片段后再比较，把片段相同误解成字符级回文。
  • 已经匹配仍选择更长外层，可能把原本能拆开的多段合并，减少答案。
  • 候选长度超过剩余长度一半，会让同一字符同时属于左右两段。
  • 未匹配就移动某一侧边界，会丢掉必须覆盖的字符。
  • 没找到匹配时返回当前计数，遗漏了剩余整体仍能作为一个中心段。

相似题目

题目 难度 关联与区别
1392. 最长快乐前缀 困难 两题都比较相同前后缀，原题取最长非整串前后缀，本题贪心取最短匹配块以获得更多分段。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2020/78391349
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！