LeetCode 1147. 段式回文
难度： h a r d \color{red}{hard} hard
题目描述
你会得到一个字符串 t e x t text text 。你应该把它分成 k k k 个子字符串 ( s u b t e x t 1 , s u b t e x t 2 ， … ， s u b t e x t k ) (subtext1, subtext2，…， subtextk) (subtext1,subtext2，…，subtextk) ，要求满足:
- s u b t e x t i subtexti subtexti 是 非空 字符串
- 所有子字符串的连接等于 t e x t text text ( 即 s u b t e x t 1 + s u b t e x t 2 + . . . + s u b t e x t k = = t e x t subtext1 + subtext2 + ... + subtextk == text subtext1+subtext2+...+subtextk==text )
- 对于所有 i 的有效值( 即 1 < = i < = k 1 <= i <= k 1<=i<=k ) ， s u b t e x t i = = s u b t e x t k − i + 1 subtexti == subtextk - i + 1 subtexti==subtextk−i+1 均成立
返回 k k 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)"。
提示：
- 1 < = t e x t . l e n g t h < = 1000 1 <= text.length <= 1000 1<=text.length<=1000
- t e x t text text 仅由小写英文字符组成
算法
(递归)
对一个字符串 text 来说，从前往后记为 left ，从后往前记为 right 如果可以划分就代表 text[left] == text[right]
只要找到相同的前后缀，就同时改变字符串 text
复杂度分析
- 时间复杂度： O ( n 2 ) O(n^2) O(n2)
C++ 代码
class Solution {
public:int longestDecomposition(string text) {if (text.empty()) return 0;for (int i = 1, n = text.length(); i <= n / 2; ++ i){if (text.substr(0, i) == text.substr(n - i)){return 2 + longestDecomposition(text.substr(i, n - i * 2));}}return 1;}
};
