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

以下是 LeetCode 3485 删除元素后 K 个字符串的最长公共前缀 的 Rust 实现。核心思路排序法参考 灵神灵茶山艾府的做法 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。rustimpl Solution {pub fn longest_common_prefix(words: VecString, k: i32) - Veci32 {let n words.len();let k k as usize;// 边界移除一个后只剩 n-1 个若 n-1 k 则全为 0if k n {return vec![0; n];}// 1. 按字符串字典序对下标排序let mut idx: Vecusize (0..n).collect();idx.sort_by(|a, b| words[a].cmp(words[b]));// 2. 辅助函数计算两个字符串的 LCP 长度fn lcp(s: str, t: str) - usize {let mut i 0;let max_len s.len().min(t.len());while i max_len s.as_bytes()[i] t.as_bytes()[i] {i 1;}i}// 3. 遍历所有长度为 k 的窗口找 mx, mx2, mx_ilet mut mx 0usize;let mut mx2 0usize;let mut mx_i 0usize;for i in 0..n - k {let 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. 构建答案let mut ans vec![mx as i32; n];// 属于最大 LCP 窗口 [mx_i, mx_i k - 1] 的原始下标答案改为 mx2for sorted_idx in idx[mx_i..mx_i k] {ans[sorted_idx] mx2 as i32;}ans}}复杂度分析指标 复杂度时间 O(n log n 总字符数) — 排序 O(n log n)所有 LCP 计算的总比较次数受限于字符串总长度≤ 10^5空间 O(n) — 下标数组 答案数组说明- 排序时只排下标不移动原字符串保证能追溯到每个元素的原始位置。- lcp 函数直接按字节比较题目保证全为小写英文字母无需处理 Unicode 多字节字符。- 当 mx 窗口内有多个相同字符串时移除其中一个可能导致窗口内仍剩 k 个相同字符串但按照排序后的窗口定义该特定窗口已被破坏此时答案退化为 mx2这在题解中已被证明是正确的若 mx2 与 mx 有交集则 mx2 一定是 mx 的前缀仍能满足。