1147. Longest Chunked Palindrome Decomposition

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 同步地址:

https://github.com/grandyang/leetcode/issues/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 题目讲解汇总(持续更新中…)


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

×

Help us with donation