以下是 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]| ≤ 1e5D maxDepth ≤ 1e5。---Python3 代码pythonfrom typing import Listclass 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 0for 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 0for 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 0for c in word:node trie[node][0][c]if trie[node][1] k:fragile[i].append(trie[node][2])# ---------- 4. 迭代线段树维护最大有效深度 ----------size 1while size max_depth:size 1# tree[i] 该区间最大有效深度无效为 -1tree [-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 - 1tree[idx] pos if val 0 else -1idx 1while idx:tree[idx] max(tree[2 * idx], tree[2 * idx 1])idx 1# ---------- 5. 枚举删除每个单词 ----------for i in range(n):# 临时删除fragile 深度上的有效节点数减 1for 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]\| ≤ 1e5D maxDepth ≤ 1e5空间 O(L D)Trie 节点数 线段树 辅助数组该解法通过 Trie 精确追踪每个前缀的覆盖次数配合迭代线段树实现高效的删除-查询-恢复是此题的标准最优解。