豆包 LeetCode 2223. 构造字符串的总得分和 JavaScript实现

LeetCode 2223 构造字符串的总得分和 JavaScript 版（Z 算法，O(n) 最优解）

这道题暴力匹配会直接超时（字符串长度可达 10^6），必须用Z 算法才能在 JavaScript 中通过所有用例。

题目核心

对每个下标i，计算s和后缀s[i:]的最长公共前缀长度，把所有长度相加就是答案。
Z 数组的定义刚好就是这个长度，所以答案 = Z 数组求和。

JavaScript 完整可提交代码

/** * @param {string} s * @return {number} */varsumScores=function(s){constn=s.length;constZ=newArray(n).fill(0);Z[0]=n;// 整个字符串和自己匹配，长度为 nletl=0,r=0;// 维护当前最右匹配区间 [l, r]for(leti=1;i<n;i++){// 1. 利用已有的区间加速计算if(i<=r){Z[i]=Math.min(r-i+1,Z[i-l]);}// 2. 暴力扩展匹配while(i+Z[i]<n&&s[Z[i]]===s[i+Z[i]]){Z[i]++;}// 3. 更新最右区间if(i+Z[i]-1>r){l=i;r=i+Z[i]-1;}}// 求和就是答案returnZ.reduce((a,b)=>a+b,0);};

代码关键说明

1. Z 数组含义

• Z[0] = 字符串长度（题目要求必须计入）
• Z[i]= 字符串前缀s[0...]与后缀s[i...]的最长公共前缀长度

2. 双指针优化（核心）

• l：当前最长匹配区间的左边界
• r：当前最长匹配区间的右边界
• 作用：避免重复匹配，让算法从 O(n²) 降到O(n)，支持 1e6 长度字符串

3. 求和

直接用reduce把 Z 数组所有值相加，就是题目要求的总得分和。

复杂度

• 时间复杂度：O(n)
• 空间复杂度：O(n)
• 支持 JavaScript 最大字符串限制，能完美通过所有测试用例

总结

1. 这题本质就是求 Z 数组 + 求和
2. 暴力解法 O(n²) 必超时，Z 算法是唯一最优解
3. 代码是标准 Z 算法模板，可直接复用

需要我给你讲Z 算法的直观理解或者测试用例演示吗？