3485. 删除 K 个字符串后的最长公共前缀

Hard

题目描述

给定一个字符串数组 words 和一个整数 k。

对于范围 [0, words.length - 1] 中的每个索引 i，找到从剩余数组中移除第 i 个元素后，任意 k 个字符串（在不同索引处选择）之间的最长公共前缀的长度。

返回一个数组 answer，其中 answer[i] 是第 i 个元素的答案。如果移除第 i 个元素后数组中的字符串少于 k 个，则 answer[i] 为 0。

示例 1：

输入：words = ["jump","run","run","jump","run"], k = 2
输出：[3,4,4,3,4]

解释：

移除索引 0（“jump”）：words 变为 [“run”, “run”, “jump”, “run”]。“run” 出现 3 次。选择其中任意两个得到最长公共前缀 “run”（长度 3）。
移除索引 1（“run”）：words 变为 [“jump”, “run”, “jump”, “run”]。“jump” 出现两次。选择这两个得到最长公共前缀 “jump”（长度 4）。

示例 2：

输入：words = ["dog","racer","car"], k = 2
输出：[0,0,0]

解释：移除任何索引都会导致答案为 0。

约束条件：

1 <= k <= words.length <= 10^5
1 <= words[i].length <= 10^4
words[i] 由小写英文字母组成
words[i].length 的总和小于等于 10^5

解题思路

这是一道需要使用字典树（Trie）优化的字符串处理问题。

核心思路：

构建字典树存储所有字符串，每个节点维护经过该节点的字符串数量
对于每个要移除的字符串，从字典树中移除并更新计数
在更新后的字典树中找到深度最大且至少有 k 个字符串经过的节点

具体步骤：

建树阶段：将所有字符串插入字典树，每个节点记录经过的字符串数量
查询阶段：对每个索引 i：
- 从字典树中移除 words[i]（减少相应路径上的计数）
- 从根节点开始深度优先搜索，找到最深的满足计数 ≥ k 的节点
- 将该字符串重新加入字典树（恢复计数）

时间复杂度优化：由于总字符长度有限制，可以有效控制字典树的大小和遍历深度。

推荐解法：字典树 + 动态计数，通过临时移除和恢复来模拟每种情况。

代码实现

class Solution {
public:
    struct TrieNode {
        TrieNode* children[26];
        int count;
        
        TrieNode() {
            for (int i = 0; i < 26; i++) {
                children[i] = nullptr;
            }
            count = 0;
        }
    };
    
    TrieNode* root;
    
    void insert(const string& word, int delta) {
        TrieNode* node = root;
        for (char c : word) {
            int idx = c - 'a';
            if (!node->children[idx]) {
                node->children[idx] = new TrieNode();
            }
            node = node->children[idx];
            node->count += delta;
        }
    }
    
    int findMaxDepth(TrieNode* node, int k) {
        if (!node || node->count < k) {
            return 0;
        }
        
        int maxDepth = 0;
        for (int i = 0; i < 26; i++) {
            if (node->children[i]) {
                maxDepth = max(maxDepth, findMaxDepth(node->children[i], k));
            }
        }
        
        return maxDepth + 1;
    }
    
    vector<int> longestCommonPrefix(vector<string>& words, int k) {
        root = new TrieNode();
        
        // Build the trie
        for (const string& word : words) {
            insert(word, 1);
        }
        
        vector<int> result;
        for (int i = 0; i < words.size(); i++) {
            // Remove the word temporarily
            insert(words[i], -1);
            
            // Find the maximum depth
            int depth = findMaxDepth(root, k);
            result.push_back(max(0, depth - 1));
            
            // Add the word back
            insert(words[i], 1);
        }
        
        return result;
    }
};

class Solution:
    def longestCommonPrefix(self, words: List[str], k: int) -> List[int]:
        class TrieNode:
            def __init__(self):
                self.children = {}
                self.count = 0
        
        def insert(word, delta):
            node = root
            for c in word:
                if c not in node.children:
                    node.children[c] = TrieNode()
                node = node.children[c]
                node.count += delta
        
        def find_max_depth(node, k):
            if not node or node.count < k:
                return 0
            
            max_depth = 0
            for child in node.children.values():
                max_depth = max(max_depth, find_max_depth(child, k))
            
            return max_depth + 1
        
        root = TrieNode()
        
        # Build the trie
        for word in words:
            insert(word, 1)
        
        result = []
        for i in range(len(words)):
            # Remove the word temporarily
            insert(words[i], -1)
            
            # Find the maximum depth
            depth = find_max_depth(root, k)
            result.append(max(0, depth - 1))
            
            # Add the word back
            insert(words[i], 1)
        
        return result

public class Solution {
    public class TrieNode {
        public TrieNode[] Children = new TrieNode[26];
        public int Count = 0;
    }
    
    private TrieNode root;
    
    private void Insert(string word, int delta) {
        TrieNode node = root;
        foreach (char c in word) {
            int idx = c - 'a';
            if (node.Children[idx] == null) {
                node.Children[idx] = new TrieNode();
            }
            node = node.Children[idx];
            node.Count += delta;
        }
    }
    
    private int FindMaxDepth(TrieNode node, int k) {
        if (node == null || node.Count < k) {
            return 0;
        }
        
        int maxDepth = 0;
        for (int i = 0; i < 26; i++) {
            if (node.Children[i] != null) {
                maxDepth = Math.Max(maxDepth, FindMaxDepth(node.Children[i], k));
            }
        }
        
        return maxDepth + 1;
    }
    
    public int[] LongestCommonPrefix(string[] words, int k) {
        root = new TrieNode();
        
        // Build the trie
        foreach (string word in words) {
            Insert(word, 1);
        }
        
        int[] result = new int[words.Length];
        for (int i = 0; i < words.Length; i++) {
            // Remove the word temporarily
            Insert(words[i], -1);
            
            // Find the maximum depth
            int depth = FindMaxDepth(root, k);
            result[i] = Math.Max(0, depth - 1);
            
            // Add the word back
            Insert(words[i], 1);
        }
        
        return result;
    }
}

var longestCommonPrefix = function(words, k) {
    class TrieNode {
        constructor() {
            this.children = {};
            this.count = 0;
        }
    }
    
    const root = new TrieNode();
    
    function insert(word, delta) {
        let node = root;
        for (const c of word) {
            if (!node.children[c]) {
                node.children[c] = new TrieNode();
            }
            node = node.children[c];
            node.count += delta;
        }
    }
    
    function findMaxDepth(node, k) {
        if (!node || node.count < k) {
            return 0;
        }
        
        let maxDepth = 0;
        for (const child of Object.values(node.children)) {
            maxDepth = Math.max(maxDepth, findMaxDepth(child, k));
        }
        
        return maxDepth + 1;
    }
    
    // Build the trie
    for (const word of words) {
        insert(word, 1);
    }
    
    const result = [];
    for (let i = 0; i < words.length; i++) {
        // Remove the word temporarily
        insert(words[i], -1);
        
        // Find the maximum depth
        const depth = findMaxDepth(root, k);
        result.push(Math.max(0, depth - 1));
        
        // Add the word back
        insert(words[i], 1);
    }
    
    return result;
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

操作	时间复杂度	空间复杂度
构建字典树	O(S)	O(S)
单次查询	O(S)	O(1)
总体复杂度	O(n × S)	O(S)

其中 S 是所有字符串长度之和，n 是字符串数量。由于题目限制 S ≤ 10^5，所以时间复杂度是可接受的。

题目描述#

解题思路#

代码实现#

复杂度分析#

题目描述

解题思路

代码实现

复杂度分析