LeetCode1147-段式回文

段式回文

Difficulty: 困难

段式回文 其实与 一般回文 类似，只不过是最小的单位是 一段字符 而不是 单个字母。

举个例子，对于一般回文 "abcba" 是回文，而 "volvo" 不是，但如果我们把 "volvo" 分为 "vo"、"l"、"vo" 三段，则可以认为 “(vo)(l)(vo)” 是段式回文（分为 3 段）。

给你一个字符串 text，在确保它满足段式回文的前提下，请你返回 段 的 最大数量 k。

如果段的最大数量为 k，那么存在满足以下条件的 a_1, a_2, ..., a_k：

• 每个 a_i 都是一个非空字符串；
• 将这些字符串首位相连的结果 a_1 + a_2 + ... + a_k 和原始字符串 text 相同；
• 对于所有1 <= i <= k，都有 a_i = a_{k+1 - i}。

示例 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)"。

示例 4：

输入：text = "aaa"
输出：3
解释：我们可以把字符串拆分成 "(a)(a)(a)"。

提示：

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

Solution

贪心算法 : 递归与迭代的实现

Language: C++

时间消耗: 12 ms; 空间消耗: 11.9 MB

class Solution {
public:
    int longestDecomposition(string text) {
        int n = text.size();        
        if(n == 0)
            return 0;
        for(int i = 1;i <= n/2; ++i){
           if(text.substr(0,i) == text.substr(n-i,i)){
               // 这里表示, 只要有一个最短匹配的就是最长的段式回文
               return 2 + longestDecomposition(text.substr(i,n-2*i));
           }
        }
        return 1;
    }
};

作者：mike-meng
链接：https://leetcode-cn.com/problems/longest-chunked-palindrome-decomposition/solution/di-gui-by-mike-meng-4/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

迭代

迭代时没有生成栈调用, 且判断中间子串的时候没有生成新的字符串, 仅仅只是使用索引区间进行限定,所以效率高很多.

时间消耗 8 ms 空间消耗:10.9 MB

class Solution {
public:
    int longestDecomposition(string text) {
        int res = 0;
        int prev = 0;
        int S = text.size();
        for (int i = 0; i < S / 2; ++i) {
            if ((text.substr(prev, i - prev + 1)) == text.substr(S - 1 - i, i - prev + 1)) {
                res += 2;
                prev = i + 1;
            }
        }
        // 中间剩余一个字母的情况: 奇数 或者 prev < S / 2 ,要累加1
        if (S % 2 == 1 || prev < S / 2)
            ++res;
        return res;
    }
};

作者：da-li-wang
链接：https://leetcode-cn.com/problems/longest-chunked-palindrome-decomposition/solution/c-jian-dan-bian-li-by-da-li-wang/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

代码更简洁, 不过字符串的累加粗看起来麻烦一些, 并且这样的效率比上面的迭代要低不少,还不如递归效率高

时间消耗:16 ms; 空间消耗:19.8 MB

int longestDecomposition(string S) {
        int res = 0, n = S.length();
        string l = "", r = "";
        for (int i = 0; i < n; ++i) {
            // 类似上面的截取字符串
            l = l + S[i], r = S[n - i - 1] + r;
            if (l == r)
                ++res, l = "", r = "";
        }
        return res;
}

作者：lee215
链接: https://leetcode.com/problems/longest-chunked-palindrome-decomposition/discuss/350560/JavaC%2B%2BPython-Easy-Greedy-with-Prove

上面两种实现方式思想都是一样的, 都是贪心算法, 这里难点是要证明从原始字符串的两端用双指针进行判断两端最短相同子串时,计算的段是最大的值.

总结: 此题使用贪心效率最高, 解题时递归求解并不一定就比迭代效率要低, 尾递归重用函数调用栈,效率很高.

贪心证明

国际版证明