力扣---1147. 段式回文-JZTXT

你会得到一个字符串 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)(tpe)(za)(pre)(a)(nt)(a)"。

提示：

1 <= text.length <= 1000
text 仅由小写英文字符组成

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/longest-chunked-palindrome-decomposition
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

最基础的是用贪心法，从两端开始贪心，遇到相同的字符串后加入答案。此时时间复杂度是 O(n^2) 。

本来想用前缀和来把时间复杂度优化成 O(n)，即利用前缀和将匹配字符串的时间复杂度降到 O(1)，但想不到一个合适的前缀和策略，只能作罢。

官解给了个哈希解，但看不懂。。。

只写了个最基础的解。

class Solution {
    //    贪心，从两边开始遍历，第一次遇到匹配的就加到结果中，然后继续开始匹配。
    public int longestDecomposition (String text) {
        int left = 0;
        int right = text.length() - 1;
        int res = 0;
        while (left < right) {
            int tem1 = left + 1;
            int tem2 = right;
            while (!judge(text, left, tem1, tem2)) {
                tem1++;
                tem2--;
                if (tem1 > tem2) {
//                    此时，说明中间的一段字符是一个整体，不能分割。
//                    返回的结果需要加一。
                    return res + 1;
                }
            }
            left = tem1;
            right = tem2 - 1;
//            左右对称，加 2 处理。
            res += 2;
        }
//        如果 text 的长度是奇数的话，如果中间部分的字符没有作为一个整体，那么必定会剩下一个。比如 aaa，aba。
//        此时，需要对答案进行加一处理。
        return text.length() % 2 == 0 ? res : res + 1;
    }

    private boolean judge (String text, int left, int tem1, int tem2) {
//        遍历，判断两个字符串是否相等。
        while (left < tem1) {
            if (text.charAt(left) != text.charAt(tem2)) {
                return false;
            }
            tem2++;
            left++;
        }
        return true;
    }
}