LeetCode 题解工作台
段式回文
你会得到一个字符串 text 。你应该把它分成 k 个子字符串 (subtext1, subtext2，…， subtextk) ，要求满足: subtext i 是 非空 字符串 所有子字符串的连接等于 text ( 即 subtext 1 + subtext 2 + ... + subtext …
6
题型
5
代码语言
3
相关题
当前训练重点
困难 · 状态·转移·动态规划
答案摘要
我们可以从字符串的两端开始，寻找长度最短的、相同且不重叠的前后缀： - 如果找不到这样的前后缀，那么整个字符串作为一个段式回文，答案加 ；
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
你会得到一个字符串 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)(tep)(za)(pre)(a)(nt)(a)"。
提示：
1 <= text.length <= 1000text仅由小写英文字符组成
解题思路
方法一：贪心 + 双指针
我们可以从字符串的两端开始，寻找长度最短的、相同且不重叠的前后缀：
- 如果找不到这样的前后缀，那么整个字符串作为一个段式回文，答案加 ；
- 如果找到了这样的前后缀，那么这个前后缀作为一个段式回文，答案加 ，然后继续寻找剩下的字符串的前后缀。
以上贪心策略的证明如下：
假设有一个前后缀 和 满足条件，又有一个前后缀 和 满足条件，由于 ，且 ，那么有 ，并且 ，因此，如果我们贪心地将 和 分割出来，那么剩下的 和 ，以及 和 也能成功分割。因此我们应该贪心地选择长度最短的相同前后缀进行分割，这样剩余的字符串中，将可能分割出更多的段式回文串。
时间复杂度 ，空间复杂度 或 。其中 为字符串的长度。
class Solution:
def longestDecomposition(self, text: str) -> int:
ans = 0
i, j = 0, len(text) - 1
while i <= j:
k = 1
ok = False
while i + k - 1 < j - k + 1:
if text[i : i + k] == text[j - k + 1 : j + 1]:
ans += 2
i += k
j -= k
ok = True
break
k += 1
if not ok:
ans += 1
break
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
The candidate demonstrates the ability to apply dynamic programming principles effectively.
- question_mark
The candidate shows understanding of optimization techniques like rolling hash for substring comparisons.
- question_mark
The candidate can combine multiple strategies, including two-pointer and greedy approaches, to solve the problem efficiently.
常见陷阱
外企场景- error
Not properly handling edge cases like very small strings or strings with no palindromes.
- error
Failing to optimize the palindrome check, leading to inefficiencies in time complexity.
- error
Not properly implementing the state transition dynamic programming approach, resulting in incorrect outputs.
进阶变体
外企场景- arrow_right_alt
The problem can be modified to include constraints like requiring each substring to be of even length.
- arrow_right_alt
Allowing only certain types of palindromes (e.g., odd-length ones) introduces further complexity.
- arrow_right_alt
Changing the input string to a set of characters or more complex symbols could lead to a variation in the approach.