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]| ≤ 1e5D maxDepth ≤ 1e5。---Java 代码javaimport java.util.*;class Solution {public int[] longestCommonPrefix(String[] words, int k) {int n words.length;int[] ans new int[n];// 删除后剩余不足 k 个直接全 0if (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 ----------ListTrieNode allNodes new ArrayList();QueueTrieNode 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 的节点深度删除后该节点会失效ListInteger[] 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 深度上的有效节点数减 1for (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 的值更新为 valval 为该深度上 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]\| ≤ 1e5D maxDepth ≤ 1e5空间 O(L D)Trie 节点数 线段树 辅助数组该解法通过 Trie 精确追踪每个前缀的覆盖次数配合线段树实现高效的删除-查询-恢复是此题的标准最优解。