段式回文
难度:
标签:
题目描述
代码结果
运行时间: 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时就返回长度作为递归的基?
▷🦆
在查找相同前后缀的循环中,为什么是使用 `while s[:i] != s[-i:]` 来增加i的值?这样的条件判断是否能保证找到最长的对称前后缀?
▷🦆
递归调用 `dfs(s[i:-i])` 时,如果中间部分长度为0,这种情况下的返回值和对结果的影响是什么?
▷🦆
在递归过程中,函数如何确保每次都能正确地增加对称段的数量?
▷