leetcode
leetcode 1951 ~ 2000
构造字符串的总得分和

构造字符串的总得分和

难度:

标签:

题目描述

代码结果

运行时间: 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算法的前缀函数来解决问题?
在这个题目中,目标是计算字符串s的每个后缀与整个字符串的最长公共前缀。KMP算法的前缀函数是处理字符串匹配问题的高效工具,它能够快速计算出字符串中每个前缀与后缀的最大公共元素的长度。利用前缀函数能够以线性时间复杂度内完成这个任务,这是因为前缀函数本质上就是为了解决类似问题而设计的。因此,使用KMP的前缀函数可以直接应用于计算字符串的每个后缀和整个字符串的匹配长度,从而高效地解决问题。
🦆
在计算前缀函数时,为什么在遇到不匹配的情况下要使用`c = pi[c - 1]`来回退?这种回退的逻辑是如何确保正确性的?
在计算前缀函数时,当当前字符不匹配时使用`c = pi[c - 1]`进行回退,是为了找到一个较短的已知前缀,该前缀仍然是当前考虑的后缀的一部分。这种逻辑的正确性在于:如果长前缀失败了,则可以尝试在此前缀的基础上最长的合法前缀,因为这仍然可能是一个有效的匹配开始。这种方式确保了算法不会漏掉可能的匹配前缀,同时避免重复检查已经失败的匹配,从而保持算法的高效性。
🦆
如何理解递归计算得分`f[i] = f[pi[i] - 1] + 1`?这里的`+1`代表什么意义?
递归计算得分`f[i] = f[pi[i] - 1] + 1`的意义在于,`f[i]`表示以索引`i`结尾的子字符串的得分,而`pi[i] - 1`是这个子字符串最长公共前后缀的前一个字符的索引。因此,`f[pi[i] - 1]`表示最长公共前后缀的得分。`+1`代表当前子字符串相较于其前缀函数指示的前一子字符串,额外增加的一个匹配单元,即当前字符本身也构成了一个有效匹配的单元。
🦆
在计算得分数组f时,为何可以保证`pi[i] - 1`总是一个有效的索引?会不会出现负索引的情况?
在计算得分数组`f`时,可以保证`pi[i] - 1`总是一个有效的索引,这是因为`pi[i]`的值始终大于等于0(即至少是0)。当`pi[i]`为0时,`pi[i] - 1`结果为-1,通常用于表示不存在前缀的情况。在实际计算`f[i]`时,需要检查`pi[i]`是否为0来避免负索引访问数组`f`。如果`pi[i]`是0,则`f[i] = 1`,表示只有当前字符自身形成长度为1的新得分。因此,算法中需要适当处理这种边界情况,以确保不会出现数组越界错误。

相关问题