[LeetCode] 1147. Longest Chunked Palindrome Decomposition 段式回文
2021/7/4 6:21:10
本文主要是介绍[LeetCode] 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 ofi
(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 题目讲解汇总(持续更新中...)
这篇关于[LeetCode] 1147. Longest Chunked Palindrome Decomposition 段式回文的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-05feign默认connecttimeout和readtimeout是多少-icode9专业技术文章分享
- 2024-07-05idea控制台,日志太多,导致部分想看得日志被刷走 搜不到-icode9专业技术文章分享
- 2024-07-05The server selected protocol version Tls10 is not accepted by client preferences [TLs12]-icode9专业技术文章分享
- 2024-07-05怎么清理项目缓存-icode9专业技术文章分享
- 2024-07-04安装 Eyoucms详细图文教程-icode9专业技术文章分享
- 2024-07-04ueditor 复制文章时,图片的链接是一个下载图片地址,该如何处理?-icode9专业技术文章分享
- 2024-07-04怎样判断host有没有对wordpress有缓存呢-icode9专业技术文章分享
- 2024-07-04具有编译功能的系统make后,无法ssh连接-icode9专业技术文章分享
- 2024-07-04make后如何升级ssh-icode9专业技术文章分享
- 2024-07-03微信支付提示下单账户与支付账户不一致-icode9专业技术文章分享