段式回文

难度: Hard

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

subtext_i是非空字符串
所有子字符串的连接等于 text ( 即subtext₁ + subtext₂ + ... + subtext_k == text )
对于所有 i 的有效值( 即 1 <= i <= k ) ，subtext_i == subtext_{k - 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 <= 1000
text 仅由小写英文字符组成

Submission

运行时间: 26 ms

内存: 16.2 MB

class Solution:
    def longestDecomposition(self, text: str) -> int:
        def dfs(s):
            if len(s) <= 1: return len(s)
            i = 1
            while s[:i] != s[-i:]: i += 1
            return 1 + dfs(s[i:-i]) + (i != len(s))
        return dfs(text)

Explain

这道题解采用了递归的方式来解决问题。首先，定义一个辅助函数dfs来处理子问题，它尝试找到字符串s的最长对称拆分。函数从字符串s的两端开始比较，尝试找到最长的相同的前后缀。如果找到了，就把这两部分作为一个合法的对称段，然后在剩下的中间部分继续递归处理。递归停止的条件是当字符串长度为1或者0时，因为这时字符串本身就是最小的对称单元或者没有字符可比较。最终，函数计算出所有这些对称段的数量，即为问题的解。

时间复杂度: O(n^2)

空间复杂度: O(n)

class Solution:
    def longestDecomposition(self, text: str) -> int:
        def dfs(s):
            # 如果字符串长度为0或1，返回长度，递归基
            if len(s) <= 1: return len(s)
            i = 1
            # 寻找最长的相同前后缀
            while s[:i] != s[-i:]: i += 1
            # 递归处理剩下的中间部分，并计算对称段的数量
            return 1 + dfs(s[i:-i]) + (i != len(s))
        return dfs(text)

Explore

在递归函数中，当字符串长度为0或1时返回长度作为递归的基是因为这些情况下字符串已经达到了最小可能的段。长度为0的字符串没有内容，自然没有对称段；长度为1的字符串是自身对称，因此直接是一个对称段。这样的递归基是处理递归问题时简化问题并防止无限递归的关键步骤。

在这个循环中，使用 `while s[:i] != s[-i:]` 来增加 `i` 的值是为了找到最长的对称前后缀。循环的条件是前缀和后缀不相等，这意味着只要前后缀不匹配，`i` 就会增加。这种方法确保了一旦找到一对匹配的前后缀，循环就会停止，此时的 `i` 就代表了最长对称前后缀的长度。因此，这种判断确实可以保证找到最长的对称前后缀。

当递归调用 `dfs(s[i:-i])` 时，如果中间部分长度为0，意味着前后缀已经覆盖了整个字符串，没有剩余的中间部分可供进一步分解。在这种情况下，`dfs(s[i:-i])` 即 `dfs('')` 将返回0，因为长度为0的字符串没有对称段。这对结果的影响是，在计算对称段总数时，这部分不会对段数有任何贡献，对称段数仅由外部的对称前后缀贡献。

递归过程中，函数通过每次成功找到对称前后缀时增加对称段的计数来确保每次都正确地增加对称段的数量。每当找到一对对称前后缀，函数就将对称段数增加1，然后继续在剩余的中间部分递归调用 `dfs`，进一步增加从中间部分找到的对称段数。通过这种方式，函数可以准确地累计所有对称段的总数，从而得到最终的结果。