Leetcode 1147:段式回文(超详细的解法!!!)
in leetcode with 0 comment

Leetcode 1147:段式回文(超详细的解法!!!)

in leetcode with 0 comment

layout: post
title: Leetcode 1147:段式回文(超详细的解法!!!)
category : 算法
tags : [python, c, c++]
stickie: true

date: 2019-8-5 00:00:00

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

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

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

如果段的最大数量为 k,那么存在满足以下条件的 a_1, a_2, ..., a_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)"。

示例 4:

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

提示:

解题思路

这个问题可以使用贪心的策略来解决,也就是每次从两边开始找最少匹配的字符串。

class Solution:
    def longestDecomposition(self, text: str) -> int:
        n = len(text)
        for i in range(1, n//2 + 1):
            if text[:i] == text[n-i:n]:
                return 2 + self.longestDecomposition(text[i:n-i])
        return 0 if n == 0 else 1

是不是很简洁,但是这么做为什么是对的呢?

假设我们同时存在一个长的前后匹配和一个短的前后匹配。此时有两种情况:

第一种就是短的匹配的长度len(shorter)<=len(longer),也就是上图,此时B1==B2R1==R4。由于B1==B2,那么R1==R3,也就是说R1==R2==R3==R4。那么如果采用短的前后匹配的话(也就是R1&R4R2&R3这样匹配),我们就多出了两种匹配(最后结果多了4

第二种就是短的匹配的长度len(shorter)>len(longer),也就是上图,此时B1==B2R1==R4。分析方法同上,不难推测出此时仍然成立。

reference:

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/350625/Java-4-Line-Solution-1-ms-100

我将该问题的其他语言版本添加到了我的GitHub Leetcode

如有问题,希望大家指出!!!

「如果我的文章对你有很大帮助,那么不妨~!」

coordinate

谢谢老板O(∩_∩)O~

使用微信扫描二维码完成支付

Responses