leetcode
leetcode 1051 ~ 1100
段式回文

段式回文

难度:

标签:

题目描述

代码结果

运行时间: 26 ms, 内存: 16.2 MB


/*
 * Solution approach:
 * 1. This solution uses a functional style to solve the problem.
 * 2. We utilize streams to iterate over potential lengths of matching substrings.
 * 3. A filter checks if the current split creates matching substrings.
 * 4. We calculate the maximum k based on valid pairs found.
 */
import java.util.stream.IntStream;
public class Solution {
    public int maxK(String text) {
        int n = text.length();
        return IntStream.range(0, n / 2 + 1)
                .filter(len -> IntStream.range(0, len)
                        .allMatch(i -> text.charAt(i) == text.charAt(n - len + i)))
                .map(len -> 2)
                .reduce((k, x) -> k + x)
                .orElse(0) + (n % 2 == 1 ? 1 : 0);
    }
}

解释

方法:

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

时间复杂度:

O(n^2)

空间复杂度:

O(n)

代码细节讲解

🦆
在递归函数中,为什么选择当字符串长度为0或1时就返回长度作为递归的基?
在递归函数中,当字符串长度为0或1时返回长度作为递归的基是因为这些情况下字符串已经达到了最小可能的段。长度为0的字符串没有内容,自然没有对称段;长度为1的字符串是自身对称,因此直接是一个对称段。这样的递归基是处理递归问题时简化问题并防止无限递归的关键步骤。
🦆
在查找相同前后缀的循环中,为什么是使用 `while s[:i] != s[-i:]` 来增加i的值?这样的条件判断是否能保证找到最长的对称前后缀?
在这个循环中,使用 `while s[:i] != s[-i:]` 来增加 `i` 的值是为了找到最长的对称前后缀。循环的条件是前缀和后缀不相等,这意味着只要前后缀不匹配,`i` 就会增加。这种方法确保了一旦找到一对匹配的前后缀,循环就会停止,此时的 `i` 就代表了最长对称前后缀的长度。因此,这种判断确实可以保证找到最长的对称前后缀。
🦆
递归调用 `dfs(s[i:-i])` 时,如果中间部分长度为0,这种情况下的返回值和对结果的影响是什么?
当递归调用 `dfs(s[i:-i])` 时,如果中间部分长度为0,意味着前后缀已经覆盖了整个字符串,没有剩余的中间部分可供进一步分解。在这种情况下,`dfs(s[i:-i])` 即 `dfs('')` 将返回0,因为长度为0的字符串没有对称段。这对结果的影响是,在计算对称段总数时,这部分不会对段数有任何贡献,对称段数仅由外部的对称前后缀贡献。
🦆
在递归过程中,函数如何确保每次都能正确地增加对称段的数量?
递归过程中,函数通过每次成功找到对称前后缀时增加对称段的计数来确保每次都正确地增加对称段的数量。每当找到一对对称前后缀,函数就将对称段数增加1,然后继续在剩余的中间部分递归调用 `dfs`,进一步增加从中间部分找到的对称段数。通过这种方式,函数可以准确地累计所有对称段的总数,从而得到最终的结果。

相关问题