段式回文【LC1147】
你会得到一个字符串
text。你应该把它分成k个子字符串(subtext1, subtext2，…， subtextk)，要求满足:
subtexti是 非空 字符串- 所有子字符串的连接等于
text( 即subtext1 + subtext2 + ... + subtextk == text)
- 对于所有 i 的有效值( 即
1 <= i <= k) ，subtexti == subtextk - i + 1均成立返回
k可能最大值。
思路
使用双指针定位前缀后缀字符串，从小到大枚举每一个长度直至前缀后缀相等时【贪心】，在该位置进行分割，然后在剩余字符串中继续匹配最短的前缀和后缀，直至左指针大于右指针时，此时无法再进行分割
由于题目要求获得最大的k，因此每次分割时的字符串长度该尽可能小
实现
class Solution { public int longestDecomposition(String text) { int n = text.length(); int l = 0, r = n - 1, len = 1; int res = 0; while (l < r - len + 1){ if (text.substring(l, l + len).equals(text.substring(r - len + 1, r + 1))){ res += 2; l += len; r -= len; len = 1; }else{ len++; } } return res + (l <= r ? 1 : 0); } }
