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

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

思路

核心思路是 Trie + 线段树：

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

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

---

Java 代码

```java
import java.util.*;

class Solution {
public int[] longestCommonPrefix(String[] words, int k) {
int n = words.length;
int[] ans = new int[n];

// 删除后剩余不足 k 个，直接全 0
if (n - 1 < k) {
return ans;
}

// ---------- 1. 构建 Trie ----------
TrieNode root = new TrieNode();
for (String word : words) {
TrieNode node = root;
for (char c : word.toCharArray()) {
int idx = c - 'a';
if (node.children[idx] == null) {
node.children[idx] = new TrieNode();
node.children[idx].depth = node.depth + 1;
}
node = node.children[idx];
node.count++;
}
}

// ---------- 2. BFS 收集所有节点，求 maxDepth ----------
List<TrieNode> allNodes = new ArrayList<>();
Queue<TrieNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
TrieNode node = queue.poll();
if (node != root) {
allNodes.add(node);
}
for (int i = 0; i < 26; i++) {
if (node.children[i] != null) {
queue.offer(node.children[i]);
}
}
}

int maxDepth = 0;
for (TrieNode node : allNodes) {
if (node.count >= k) {
maxDepth = Math.max(maxDepth, node.depth);
}
}

// 没有任何前缀被 >= k 个字符串共享
if (maxDepth == 0) {
return ans;
}

// globalCount[d] = 深度 d 上 count >= k 的节点数量
int[] globalCount = new int[maxDepth + 1];
for (TrieNode node : allNodes) {
if (node.count >= k && node.depth <= maxDepth) {
globalCount[node.depth]++;
}
}

// ---------- 3. 找每个单词的 fragile depths ----------
// fragile: 路径上 count == k 的节点深度，删除后该节点会失效
List<Integer>[] fragile = new ArrayList[n];
for (int i = 0; i < n; i++) {
fragile[i] = new ArrayList<>();
TrieNode node = root;
for (char c : words[i].toCharArray()) {
node = node.children[c - 'a'];
if (node.count == k) {
fragile[i].add(node.depth);
}
}
}

// ---------- 4. 线段树维护每个深度是否有效 ----------
SegmentTree seg = new SegmentTree(maxDepth, globalCount);

// ---------- 5. 枚举删除每个单词 ----------
for (int i = 0; i < n; i++) {
// 临时删除：fragile 深度上的有效节点数减 1
for (int d : fragile[i]) {
seg.update(1, 1, maxDepth, d, globalCount[d] - 1);
}
int res = seg.query();
ans[i] = res == -1 ? 0 : res;
// 恢复
for (int d : fragile[i]) {
seg.update(1, 1, maxDepth, d, globalCount[d]);
}
}

return ans;
}

// Trie 节点
class TrieNode {
TrieNode[] children = new TrieNode[26];
int count = 0; // 经过该节点的字符串数
int depth = 0; // 该节点代表的前缀长度
}

// 线段树：维护每个深度是否有效，查询最大有效深度
class SegmentTree {
int n;
int[] tree;
int[] globalCount;

SegmentTree(int n, int[] globalCount) {
this.n = n;
this.globalCount = globalCount;
this.tree = new int[4 * (n + 1)];
build(1, 1, n);
}

void build(int node, int l, int r) {
if (l == r) {
tree[node] = globalCount[l] > 0 ? l : -1;
return;
}
int mid = (l + r) >> 1;
build(node << 1, l, mid);
build(node << 1 | 1, mid + 1, r);
tree[node] = Math.max(tree[node << 1], tree[node << 1 | 1]);
}

// 将位置 pos 的值更新为 val（val 为该深度上 count >= k 的节点数）
void update(int node, int l, int r, int pos, int val) {
if (l == r) {
tree[node] = val > 0 ? l : -1;
return;
}
int mid = (l + r) >> 1;
if (pos <= mid) {
update(node << 1, l, mid, pos, val);
} else {
update(node << 1 | 1, mid + 1, r, pos, val);
}
tree[node] = Math.max(tree[node << 1], tree[node << 1 | 1]);
}

// 查询全局最大有效深度
int query() {
return tree[1];
}
}
}
```

---

复杂度分析

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

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