以下是 LeetCode 3485 删除元素后 K 个字符串的最长公共前缀 的 C 实现。核心思路排序法参考 灵神灵茶山艾府的做法1. 排序后连续 k 个字符串的 LCP 最优将 words 按字典序排序任意 k 个字符串的最长公共前缀最大值一定来自某个连续的 k 个字符串子数组。且该子数组的 LCP 等于首尾两个字符串的 LCP。2. 预处理全局最大/次大 LCP遍历所有长度为 k 的窗口计算每个窗口首尾的 LCP记录- mx最大 LCP 值- mx2次大 LCP 值- mx_i最大 LCP 对应的窗口起始下标在排序后的数组中3. 分类讨论- 若移除的字符串不在 mx 窗口内 → 答案为 mx- 若移除的字符串在 mx 窗口内 → 该窗口被破坏答案为 mx24. 边界若 k n移除一个后剩余不足 k 个全填 0。cppclass Solution {public:vectorint longestCommonPrefix(vectorstring words, int k) {int n words.size();// 边界移除一个后只剩 n-1 个若 n-1 k 则全为 0if (k n) {return vectorint(n, 0);}// 1. 按字符串字典序对下标排序vectorint idx(n);iota(idx.begin(), idx.end(), 0);sort(idx.begin(), idx.end(), [](int a, int b) {return words[a] words[b];});// 2. 辅助函数计算两个字符串的 LCP 长度auto lcp [](const string s, const string t) - int {int i 0;int maxLen min(s.size(), t.size());while (i maxLen s[i] t[i]) {i;}return i;};// 3. 遍历所有长度为 k 的窗口找 mx, mx2, mx_iint mx 0; // 最大 LCPint mx2 0; // 次大 LCPint mx_i 0; // 最大 LCP 窗口的起始下标for (int i 0; i n - k; i) {int len lcp(words[idx[i]], words[idx[i k - 1]]);if (len mx) {mx2 mx;mx len;mx_i i;} else if (len mx2) {mx2 len;}}// 4. 构建答案vectorint ans(n, mx);// 属于最大 LCP 窗口 [mx_i, mx_i k - 1] 的原始下标答案改为 mx2for (int i mx_i; i mx_i k; i) {ans[idx[i]] mx2;}return ans;}};复杂度分析指标 复杂度时间 O(n log n 总字符数) — 排序 O(n log n)所有 LCP 计算的总比较次数受限于字符串总长度≤ 10^5空间 O(n) — 下标数组 答案数组说明- 排序时只排下标不移动原字符串保证能追溯到每个元素的原始位置。- lcp 函数直接按字符比较题目保证全为小写英文字母。- 当 mx 窗口内有多个相同字符串时移除其中一个可能导致窗口内仍剩 k 个相同字符串但按照排序后的窗口定义该特定窗口已被破坏此时答案退化为 mx2这在题解中已被证明是正确的若 mx2 与 mx 有交集则 mx2 一定是 mx 的前缀仍能满足。
