你会得到一个字符串 text 。你应该把它分成 k 个子字符串 (subtext_1, subtext_2, ..., subtext_k)，要求满足:
- subtext_i 是非空字符串
- 所有子字符串的连接等于 text ( 即
subtext_1 + subtext_2 + ... + subtext_k == text) - 对于所有 i 的有效值 ( 即
1 <= i <= k)，subtext_i == subtext_(k - i + 1)均成立
返回 k 可能的最大值。
题目链接：https://leetcode.cn/problems/longest-chunked-palindrome-decomposition/
# 解题思路
双指针：
- l 表示左边未匹配的子串尾部
- r 表示右边未匹配的子串开始
- lm 表示 left matched，即左边已匹配的字符串结尾
- rm 表示 right matched，即右边已匹配的字符串开始
# 执行结果
# 代码
class Solution { | |
public int longestDecomposition(String text) { | |
int rm = text.length(); | |
int lm = -1; | |
int l = 0; | |
int r = text.length() - 1; | |
int cnt = 0; | |
while (l < r) { | |
if (text.substring(lm + 1, l + 1).equals(text.substring(r, rm))) { | |
cnt += 2; | |
lm = l; | |
rm = r; | |
} | |
++l; | |
--r; | |
} | |
// 已匹配的双指针没有相邻，说明中间还有一个字符串 | |
if (lm + 1 < rm) ++cnt; | |
return cnt; | |
} | |
} |
