构造字符串的总得分和
难度:
标签:
题目描述
代码结果
运行时间: 210 ms, 内存: 23.8 MB
/*
* 思路:
* 1. 初始化总得分为0。
* 2. 使用IntStream.range来生成索引。
* 3. 对每个索引应用双指针法找到最长公共前缀,并累加其长度到总得分中。
*/
import java.util.stream.IntStream;
public class Solution {
public int prefixScoreSum(String s) {
int n = s.length();
return IntStream.range(0, n)
.map(i -> {
int j = 0;
while (i + j < n && s.charAt(j) == s.charAt(i + j)) {
j++;
}
return j;
})
.sum();
}
}
解释
方法:
解题思路首先利用了一个字符串处理中的经典算法——KMP算法中的前缀函数(也称为π函数)。前缀函数可以高效地处理字符串的前缀匹配问题。具体到这个题目,我们使用前缀函数来计算字符串s的每个后缀与整个字符串的最长公共前缀。\n\n首先通过前缀函数计算得到数组pi,其中pi[i]表示字符串s[0:i+1]的最长公共前后缀的长度。然后,使用一个额外数组f来记录每个si的得分。对于每个位置i,它的得分f[i]可以通过pi数组递归得到:f[i] = f[pi[i] - 1] + 1。最后,计算f数组中所有数值的总和即可得到答案。
时间复杂度:
O(n)
空间复杂度:
O(n)
代码细节讲解
🦆
为什么在这个题目中选择使用KMP算法的前缀函数来解决问题?
▷🦆
在计算前缀函数时,为什么在遇到不匹配的情况下要使用`c = pi[c - 1]`来回退?这种回退的逻辑是如何确保正确性的?
▷🦆
如何理解递归计算得分`f[i] = f[pi[i] - 1] + 1`?这里的`+1`代表什么意义?
▷🦆
在计算得分数组f时,为何可以保证`pi[i] - 1`总是一个有效的索引?会不会出现负索引的情况?
▷