制作网站要步骤,湖北省建设厅网站上岗证查询,本地利用wordpress建站,怎么做网络彩票网站文章目录1. 题目2. 解题1. 题目
段式回文 其实与 一般回文 类似#xff0c;只不过是最小的单位是 一段字符 而不是 单个字母。
举个例子#xff0c;对于一般回文 abcba 是回文#xff0c;而 volvo 不是#xff0c;但如果我们把 volvo只不过是最小的单位是 一段字符 而不是 单个字母。
举个例子对于一般回文 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_{k1 - 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来源力扣LeetCode 链接https://leetcode-cn.com/problems/longest-chunked-palindrome-decomposition 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
贪心的做法遇到相等的前后子串就取出来循环检查剩余串证明见题解区
class Solution {
public:int longestDecomposition(string text) {int i 0, j text.size()-1, ans 0;while(i j){int maxlen j-i1;//剩余子串 [i,j]for(int len 1; len maxlen; len){if(text.substr(i,len) text.substr(j-len1, len)){ // 首尾子串 相等if(len maxlen)ans 2;elseans 1;i len;j - len;break;}}}return ans;}
};0 ms 11.3 MB C 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
