Leetcode.1147 段式回文

题目链接

Leetcode.1147 段式回文 Rating : 1912

题目描述

你会得到一个字符串 text。你应该把它分成 k 个子字符串 (subtext1, subtext2，…， subtextk) ，要求满足:

• subtexti是 非空 字符串
• 所有子字符串的连接等于 text( 即subtext1 + subtext2 + ... + subtextk == text)
• 对于所有 i 的有效值( 即 1 <= i <= k ) ，subtexti == subtextk - i + 1均成立

返回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<=text.length<=1000$
• text仅由小写英文字符组成

解法一：递归

由于我们求的是最大分段。所以当我们第一次遇到某一个长度为 $len$ 的 前缀 和 后缀 相等时，就直接将这两个前后缀分割出来，即答案 $ans+1$。

例如，给定字符串 s = "abcfabcabcfabc"，它有几种分割法：

• s = "(abcfabc) (abcfabc)"
• s = "(abc) (f) (abc) (abc) (f) (abc)"

很显然第二种分法得到的答案更多。所以正确的方法是遇到第一个相同的前后缀，就将其分割。

时间复杂度：O(n2)O(n^2)O(n2)

C++代码:

class Solution {
public:int longestDecomposition(string s) {if(s.empty()) return 0;int n = s.size();for(int i = 1;i <= n / 2;i++){//有两个相同的前后缀，故可以拆分if(s.substr(0,i) == s.substr(n - i)){return 2 + longestDecomposition(s.substr(i , n - 2*i));}}//当前 s 不能拆分，直接返回 1return 1;}
};

解法二：字符串哈希

关于字符串哈希

时间复杂度： $O(n)$

C++代码：

using ULL = unsigned long long;const int N = 1010, P = 131;
ULL h[N] , p[N];class Solution {
public:ULL get(int l,int r){return h[r] - h[l-1] * p[r-l+1];}int longestDecomposition(string s) {int n = s.size();memset(h,0,sizeof h);memset(p,0,sizeof p);p[0] = 1;for(int i = 1;i <= n;i++){p[i] = p[i-1] * P;h[i] = h[i-1] * P + s[i - 1];}int ans = 0;int l = 1 , r = n;while(l <= r){int len = (r - l + 1);bool ok = false;for(int i = 0;i <=  len / 2 && l + i < r - i;i++){if(get(l,l + i) == get(r - i , r)){ok = true;l = l + i + 1;r = r - i - 1;ans += 2;break;}}if(!ok){ans++;break;}}return ans;}
};