[LeetCode] 1147. Longest Chunked Palindrome Decomposition

[grandyang]

You are given a string text. You should split it to k substrings (subtext1, subtext2, ..., subtextk) such that:

• subtexti is a non-empty string.
• The concatenation of all the substrings is equal to text (i.e., subtext1 + subtext2 + ... + subtextk == text).
• subtexti == subtextk - i + 1 for all valid values of i (i.e., 1 <= i <= k).

Return the largest possible value of k.

Example 1:

Input: text = "ghiabcdefhelloadamhelloabcdefghi"
Output: 7
Explanation: We can split the string on "(ghi)(abcdef)(hello)(adam)(hello)(abcdef)(ghi)".

Example 2:

Input: text = "merchant"
Output: 1
Explanation: We can split the string on "(merchant)".

Example 3:

Input: text = "antaprezatepzapreanta"
Output: 11
Explanation: We can split the string on "(a)(nt)(a)(pre)(za)(tpe)(za)(pre)(a)(nt)(a)".

Example 4:

Input: text = "aaa"
Output: 3
Explanation: We can split the string on "(a)(a)(a)".

Constraints:

• 1 <= text.length <= 1000
• text consists only of lowercase English characters.

这道题是关于段式回文的，想必大家对回文串都不陌生，就是前后字符对应相同的字符串，比如 noon 和 bob。这里的段式回文相等的不一定是单一的字符，而是可以是字串，参见题目中的例子，现在给了一个字符串，问可以得到的段式回文串的最大长度是多少。由于段式回文的特点，你可以把整个字符串都当作一个子串，则可以得到一个长度为1的段式回文，所以答案至少是1，不会为0。而最好情况就是按字符分别相等，那就变成了一般的回文串，则长度就是原字符串的长度。比较的方法还是按照经典的验证回文串的方式，用双指针来做，一前一后。不同的是遇到不相等的字符不是立马退出，而是累加两个子串 left 和 right，每累加一个字符，都比较一下 left 和 right 是否相等，这样可以保证尽可能多的分出来相等的子串，一旦分出了相等的子串，则 left 和 right 重置为空串，再次从小到大比较，参见代码如下：

解法一：

class Solution {
public:
    int longestDecomposition(string text) {
        int res = 0, n = text.size();
        string left, right;
        for (int i = 0; i < n; ++i) {
            left += text[i], right = text[n - i - 1] + right;
            if (left == right) {
                ++res;
                left = right = "";
            }
        }
        return res;
    }
};

我们也可以使用递归来做，写法更加简洁一些，i从1遍历到 n/2，代表的是子串的长度，一旦超过一半了，说明无法分为两个了，最终做个判断即可。为了不每次都提取出子串直接进行比较，这里可以先做个快速的检测，即判断两个子串的首尾字符是否对应相等，只有相等了才会提取整个子串进行比较，这样可以省掉一些不必要的计算，参见代码如下：

解法二：

class Solution {
public:
    int longestDecomposition(string text) {
        int n = text.size();
        for (int i = 1; i <= n / 2; ++i) {
            if (text[0] == text[n - i] && text[i - 1] == text[n - 1]) {
                if (text.substr(0, i) == text.substr(n - i)) {
                    return 2 + longestDecomposition(text.substr(i, n - 2 * i));
                }
            }
        }
        return n == 0 ? 0 : 1;
    }
};

Github 同步地址:

#1147

类似题目：

参考资料：

https://leetcode.com/problems/longest-chunked-palindrome-decomposition/

https://leetcode.com/problems/longest-chunked-palindrome-decomposition/discuss/350560/JavaC%2B%2BPython-Easy-Greedy-with-Prove

https://leetcode.com/problems/longest-chunked-palindrome-decomposition/discuss/350762/Java-0ms-concise-beats-100-(both-time-and-memory)-with-algo

LeetCode All in One 题目讲解汇总(持续更新中...)