如何将字符串列表缩写为最短且无歧义的形式

需求说明 #

给定一个字符串数组，需要将每个元素缩写为最短且无歧义的前缀——即该前缀是当前元素独有的，数组中没有其他元素以这个前缀开头。比如输入：

let list = ["apple", "apricot", "banana", "cherry"];

对应的输出为：

["app", "apr", "b", "c"]

核心思路 #

你提到的仅对比相邻元素的思路确实有局限，因为非相邻的字符串也可能共享前缀，导致缩写冲突。正确的做法是：

• 对每个字符串，从最短前缀（长度1）开始尝试
• 检查数组中所有其他字符串是否有以当前前缀开头的
• 找到第一个没有冲突的前缀，作为该字符串的缩写

Rust 实现代码 #

fn shortest_unique_prefixes(strings: &[&str]) -> Vec<String> {
    strings.iter().map(|&s| {
        // 从长度1开始尝试前缀，直到找到唯一的
        for len in 1..=s.len() {
            let prefix = &s[0..len];
            // 检查是否有其他字符串以该前缀开头
            let has_conflict = strings.iter()
                .any(|&other| other != s && other.starts_with(prefix));
            if !has_conflict {
                return prefix.to_string();
            }
        }
        // 极端情况：字符串本身就是唯一的，直接返回原字符串
        s.to_string()
    }).collect()
}

fn main() {
    let list = ["apple", "apricot", "banana", "cherry"];
    let result = shortest_unique_prefixes(&list);
    println!("{:?}", result); // 输出: ["app", "apr", "b", "c"]
}

代码说明 #

• 外层map遍历每个字符串，为每个字符串生成缩写
• 内层循环从长度1开始生成前缀，逐个检查冲突
• any方法用于快速判断是否存在其他字符串共享当前前缀，一旦发现冲突就尝试更长的前缀
• 如果所有前缀都有冲突（比如数组里有完全相同的字符串），则返回原字符串（这种情况可根据实际需求调整处理逻辑）

内容的提问来源于stack exchange，提问作者Michael B. Ortiz