本文共 1367 字,大约阅读时间需要 4 分钟。
段式回文 其实与 一般回文 类似,只不过是最小的单位是 一段字符 而不是 单个字母。
举个例子,对于一般回文 “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
解题思路
这个问题可以使用贪心的策略来解决,也就是每次从两边开始找最少匹配的字符串。
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==B2
、R1==R4
。由于B1==B2
,那么R1==R3
,也就是说R1==R2==R3==R4
。那么如果采用短的前后匹配的话(也就是R1&R4
,R2&R3
这样匹配),我们就多出了两种匹配(最后结果多了4
)
第二种就是短的匹配的长度len(shorter)>len(longer)
,也就是上图,此时B1==B2
、R1==R4
。分析方法同上,不难推测出此时仍然成立。
reference:
我将该问题的其他语言版本添加到了我的
如有问题,希望大家指出!!!
转载地址:https://coordinate.blog.csdn.net/article/details/98498913 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!