LeetCode 题解工作台
相邻字符串之间的最长公共前缀
给你一个字符串数组 words ，对于范围 [0, words.length - 1] 内的每个下标 i ，执行以下步骤： 从 words 数组中移除下标 i 处的元素。 计算修改后的数组中所有 相邻对 之间的 最长公共前缀 的长度。 返回一个数组 answer ，其中 answer[i] 是移除下…
2
题型
4
代码语言
3
相关题
当前训练重点
中等 · 数组·string
答案摘要
我们定义一个函数 $\textit{calc}(s, t)$，它计算字符串 和 的最长公共前缀的长度。我们可以使用有序集合来维护所有相邻字符串对的最长公共前缀长度。 定义一个函数 $\textit{add}(i, j)$，它将下标 和 处的字符串对的最长公共前缀长度添加到有序集合中。定义一个函数 $\textit{remove}(i, j)$，它从有序集合中移除下标 和 处的字符串对的…
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·string 题型思路
题目描述
给你一个字符串数组 words，对于范围 [0, words.length - 1] 内的每个下标 i，执行以下步骤：
- 从
words数组中移除下标i处的元素。 - 计算修改后的数组中所有 相邻对 之间的 最长公共前缀 的长度。
返回一个数组 answer，其中 answer[i] 是移除下标 i 后，相邻对之间最长公共前缀的长度。如果 不存在 相邻对，或者 不存在 公共前缀，则 answer[i] 应为 0。
字符串的前缀是从字符串的开头开始延伸到任意位置的子字符串。
示例 1：
输入： words = ["jump","run","run","jump","run"]
输出： [3,0,0,3,3]
解释：
- 移除下标 0：
words变为["run", "run", "jump", "run"]- 最长的相邻对是
["run", "run"]，其公共前缀为"run"（长度为 3）
- 移除下标 1：
words变为["jump", "run", "jump", "run"]- 没有相邻对有公共前缀（长度为 0）
- 移除下标 2：
words变为["jump", "run", "jump", "run"]- 没有相邻对有公共前缀（长度为 0）
- 移除下标 3：
words变为["jump", "run", "run", "run"]- 最长的相邻对是
["run", "run"]，其公共前缀为"run"（长度为 3）
- 移除下标 4：
words变为["jump", "run", "run", "jump"]- 最长的相邻对是
["run", "run"]，其公共前缀为"run"（长度为 3）
示例 2：
输入： words = ["dog","racer","car"]
输出： [0,0,0]
解释：
- 移除任意下标都会导致答案为 0。
提示：
1 <= words.length <= 1051 <= words[i].length <= 104words[i]仅由小写英文字母组成。words[i]的长度总和不超过105。
解题思路
方法一：有序集合
我们定义一个函数 ，它计算字符串 和 的最长公共前缀的长度。我们可以使用有序集合来维护所有相邻字符串对的最长公共前缀长度。
定义一个函数 ，它将下标 和 处的字符串对的最长公共前缀长度添加到有序集合中。定义一个函数 ，它从有序集合中移除下标 和 处的字符串对的最长公共前缀长度。
我们首先计算所有相邻字符串对的最长公共前缀长度，并将其存储在有序集合中。然后，我们遍历每个下标 ，执行以下操作：
- 移除下标 和 处的字符串对的最长公共前缀长度。
- 移除下标 和 处的字符串对的最长公共前缀长度。
- 添加下标 和 处的字符串对的最长公共前缀长度。
- 将当前有序集合中的最大值（如果存在且大于 0）添加到答案中。
- 移除下标 和 处的字符串对的最长公共前缀长度。
- 添加下标 和 处的字符串对的最长公共前缀长度。
- 添加下标 和 处的字符串对的最长公共前缀长度。
这样，我们可以在每次移除一个字符串后，快速计算出相邻字符串对的最长公共前缀长度。
时间复杂度 ，空间复杂度 ，其中 是所有字符串的总长度，而 是字符串的数量。
class Solution:
def longestCommonPrefix(self, words: List[str]) -> List[int]:
@cache
def calc(s: str, t: str) -> int:
k = 0
for a, b in zip(s, t):
if a != b:
break
k += 1
return k
def add(i: int, j: int):
if 0 <= i < n and 0 <= j < n:
sl.add(calc(words[i], words[j]))
def remove(i: int, j: int):
if 0 <= i < n and 0 <= j < n:
sl.remove(calc(words[i], words[j]))
n = len(words)
sl = SortedList(calc(a, b) for a, b in pairwise(words))
ans = []
for i in range(n):
remove(i, i + 1)
remove(i - 1, i)
add(i - 1, i + 1)
ans.append(sl[-1] if sl and sl[-1] > 0 else 0)
remove(i - 1, i + 1)
add(i - 1, i)
add(i, i + 1)
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Look for the ability to optimize prefix calculation by reducing redundant work.
- question_mark
Evaluate how well the candidate handles edge cases, such as removing a word with no adjacent pairs.
- question_mark
Assess the ability to articulate how precomputing adjacent pair prefixes improves efficiency.
常见陷阱
外企场景- error
Failing to optimize the solution by recalculating the prefix for every removal, leading to excessive time complexity.
- error
Not properly handling edge cases like when there are no adjacent pairs or when the LCP is zero.
- error
Overcomplicating the problem by using nested loops instead of leveraging the precomputed values for adjacent pairs.
进阶变体
外企场景- arrow_right_alt
Modify the problem to handle case-insensitive strings.
- arrow_right_alt
Introduce constraints where only a certain number of removals are allowed and calculate the LCP only for those removals.
- arrow_right_alt
Extend the problem to handle words that have varying lengths and require dynamic adjustments to the prefix calculations.