LeetCode 题解工作台
构造字符串的总得分和
你需要从空字符串开始 构造 一个长度为 n 的字符串 s ，构造的过程为每次给当前字符串 前面 添加 一个 字符。构造过程中得到的所有字符串编号为 1 到 n ，其中长度为 i 的字符串编号为 s i 。 比方说， s = "abaca" ， s 1 == "a" ， s 2 == "ca" ， s…
6
题型
0
代码语言
3
相关题
当前训练重点
困难 · 二分·搜索·答案·空间
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 二分·搜索·答案·空间 题型思路
题目描述
你需要从空字符串开始 构造 一个长度为 n 的字符串 s ，构造的过程为每次给当前字符串 前面 添加 一个 字符。构造过程中得到的所有字符串编号为 1 到 n ，其中长度为 i 的字符串编号为 si 。
- 比方说，
s = "abaca"，s1 == "a"，s2 == "ca"，s3 == "aca"依次类推。
si 的 得分 为 si 和 sn 的 最长公共前缀 的长度（注意 s == sn ）。
给你最终的字符串 s ，请你返回每一个 si 的 得分之和 。
示例 1：
输入：s = "babab" 输出：9 解释： s1 == "b" ，最长公共前缀是 "b" ，得分为 1 。 s2 == "ab" ，没有公共前缀，得分为 0 。 s3 == "bab" ，最长公共前缀为 "bab" ，得分为 3 。 s4 == "abab" ，没有公共前缀，得分为 0 。 s5 == "babab" ，最长公共前缀为 "babab" ，得分为 5 。 得分和为 1 + 0 + 3 + 0 + 5 = 9 ，所以我们返回 9 。
示例 2 ：
输入：s = "azbazbzaz" 输出：14 解释： s2 == "az" ，最长公共前缀为 "az" ，得分为 2 。 s6 == "azbzaz" ，最长公共前缀为 "azb" ，得分为 3 。 s9 == "azbazbzaz" ，最长公共前缀为 "azbazbzaz" ，得分为 9 。 其他 si 得分均为 0 。 得分和为 2 + 3 + 9 = 14 ，所以我们返回 14 。
提示：
1 <= s.length <= 105s只包含小写英文字母。
解题思路
方法一
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Can the candidate identify the binary search pattern over the valid answer space?
- question_mark
Does the candidate recognize the need for rolling hashes in optimizing string comparisons?
- question_mark
Is the candidate familiar with advanced string algorithms like suffix arrays or string matching?
常见陷阱
外企场景- error
Misunderstanding the problem by calculating scores directly without considering efficient string matching techniques.
- error
Focusing too much on brute force solutions without optimizing with binary search or hashing.
- error
Incorrectly calculating the longest common prefix, especially when dealing with large strings or multiple substrings.
进阶变体
外企场景- arrow_right_alt
What if the string s contains only one character? How does that simplify the problem?
- arrow_right_alt
What if the string contains repeated substrings? How does that impact the approach?
- arrow_right_alt
How would the problem change if instead of summing the scores, we had to find the maximum score?