Kimi LeetCode 3485. 删除元素后 K 个字符串的最长公共前缀 Python3实现

以下是 LeetCode 3485 删除元素后 K 个字符串的最长公共前缀 的 Python3 实现。

思路

核心思路是 Trie + 迭代线段树：

1. 构建 Trie：将所有字符串插入字典树，每个节点记录 `count`（经过该节点的字符串数）和 `depth`（前缀长度）。
2. 统计有效深度：对于每个深度 `d`，统计 Trie 中 `count >= k` 的节点数量 `global_count[d]`。若 `global_count[d] > 0`，说明存在至少 `k` 个字符串共享长度为 `d` 的前缀，深度 `d` 有效。
3. 线段树维护：用迭代线段树维护每个深度是否有效，支持 O(log D) 的单点更新和 O(1) 的全局最大值查询。
4. 删除模拟：对于每个单词，找出它在 Trie 路径上所有 `count == k` 的节点（称为 fragile 节点）。删除该单词时，这些节点的 `count` 会变为 `k-1`，不再满足条件。临时更新线段树后查询最大有效深度，即可得到删除该单词后的答案，然后恢复。

时间复杂度 O(L · log D)，其中 `L = Σ|words[i]| ≤ 1e5`，`D = maxDepth ≤ 1e5`。

---

Python3 代码

```python
from typing import List

class Solution:
def longestCommonPrefix(self, words: List[str], k: int) -> List[int]:
n = len(words)
ans = [0] * n

# 删除后剩余不足 k 个字符串，无法选出 k 个
if n - 1 < k:
return ans

# ---------- 1. 构建 Trie ----------
# 每个节点: [children_dict, count, depth]
trie = [[{}, 0, 0]] # 根节点

for word in words:
node = 0
for c in word:
if c not in trie[node][0]:
trie[node][0][c] = len(trie)
trie.append([{}, 0, trie[node][2] + 1])
node = trie[node][0][c]
trie[node][1] += 1

# ---------- 2. 统计每个深度的有效节点数 ----------
max_depth = 0
for idx in range(1, len(trie)):
if trie[idx][1] >= k:
max_depth = max(max_depth, trie[idx][2])

# 没有任何前缀被 >= k 个字符串共享
if max_depth == 0:
return ans

# global_count[d] = 深度 d 上 count >= k 的节点数量
global_count = [0] * (max_depth + 1)
for idx in range(1, len(trie)):
if trie[idx][1] >= k and trie[idx][2] <= max_depth:
global_count[trie[idx][2]] += 1

# ---------- 3. 找每个单词的 fragile depths ----------
# fragile: 路径上 count == k 的节点深度，删除后该节点会失效
fragile = [[] for _ in range(n)]
for i, word in enumerate(words):
node = 0
for c in word:
node = trie[node][0][c]
if trie[node][1] == k:
fragile[i].append(trie[node][2])

# ---------- 4. 迭代线段树（维护最大有效深度） ----------
size = 1
while size < max_depth:
size <<= 1

# tree[i] = 该区间最大有效深度，无效为 -1
tree = [-1] * (2 * size)

# 初始化叶子节点
for d in range(1, max_depth + 1):
tree[size + d - 1] = d if global_count[d] > 0 else -1

# 初始化内部节点
for i in range(size - 1, 0, -1):
tree[i] = max(tree[2 * i], tree[2 * i + 1])

def update(pos: int, val: int):
"""将深度 pos 的有效节点数更新为 val，维护线段树"""
idx = size + pos - 1
tree[idx] = pos if val > 0 else -1
idx >>= 1
while idx:
tree[idx] = max(tree[2 * idx], tree[2 * idx + 1])
idx >>= 1

# ---------- 5. 枚举删除每个单词 ----------
for i in range(n):
# 临时删除：fragile 深度上的有效节点数减 1
for d in fragile[i]:
update(d, global_count[d] - 1)

res = tree[1]
ans[i] = res if res != -1 else 0

# 恢复
for d in fragile[i]:
update(d, global_count[d])

return ans
```

---

复杂度分析

指标 复杂度
时间 O(L · log D)，其中 `L = Σ\|words[i]\| ≤ 1e5`，`D = maxDepth ≤ 1e5`
空间 O(L + D)，Trie 节点数 + 线段树 + 辅助数组

该解法通过 Trie 精确追踪每个前缀的覆盖次数，配合迭代线段树实现高效的删除-查询-恢复，是此题的标准最优解。