如何从姓名列表中提取所有完整姓名？使用trie是否合适？

给定如下姓名列表：

names = [
         "bob john", 
         "billy james",
         "bob joe",
         "bob joe henry",
         "bob", 
         "bob john martin", 
         "billy james phillip",
         "billy james phillip mark"
]

需要筛选出列表中所有完整姓名（即不存在其他姓名是当前姓名的扩展，也就是当前姓名不是列表中其他更长姓名的前缀），预期输出如下：

full_names = [
              "bob joe henry",
              "bob john martin", 
              "billy james phillip mark" 
]

注：预期输出示例中billy James存在首字母大写笔误，原列表中为小写james，实际实现时需要注意统一大小写规则，避免匹配错误。
同时需要判断该场景下使用Trie数据结构实现需求是否合适。

轻量场景：直接遍历实现 #

如果姓名列表数据量在万级以内，不需要引入复杂数据结构，直接按长度排序后遍历判断即可，代码简单不易出错：

full_names = []
# 按姓名长度从长到短排序，更长的姓名一定不可能是短姓名的前缀扩展
sorted_names = sorted(names, key=lambda x: len(x), reverse=True)
for name in sorted_names:
    is_full_name = True
    # 检查当前姓名是否是已收录完整姓名的前缀，如果是说明它不是最长的完整姓名
    for added_name in full_names:
        if added_name.startswith(name):
            is_full_name = False
            break
    if is_full_name:
        full_names.append(name)

print(full_names)
# 输出结果：['billy james phillip mark', 'bob john martin', 'bob joe henry']

如果需要和预期输出顺序一致，最后可以再按原列表的索引排序调整顺序即可。

大数据量场景：Trie树实现 #

Trie适用性结论 #

非常适合，当数据量达到十万级甚至更高时，Trie树的前缀匹配效率远高于暴力遍历，时间复杂度可以从暴力法的O(N²)降到线性O(N)。
注意这里不要按单个字符建Trie，按姓名拆分后的词组建Trie效率更高，也能避免跨单词的误匹配（比如避免把"bob j"当成前缀匹配）。

Trie实现参考 #

class TrieNode:
    def __init__(self):
        self.children = dict()  # key是名字分段，value是子节点
        self.is_end = False

# 第一步：把所有姓名插入Trie
root = TrieNode()
for name in names:
    name_parts = name.split()
    current_node = root
    for part in name_parts:
        if part not in current_node.children:
            current_node.children[part] = TrieNode()
        current_node = current_node.children[part]
    current_node.is_end = True

# 第二步：深度遍历Trie，所有没有子节点的叶子节点对应的路径就是完整姓名
full_names = []
def traverse(node, current_path):
    # 没有子节点说明已经是最长路径，即为完整姓名
    if not node.children:
        full_names.append(" ".join(current_path))
        return
    for part, child_node in node.children.items():
        traverse(child_node, current_path + [part])

traverse(root, [])
print(full_names)
# 输出结果：['bob joe henry', 'bob john martin', 'billy james phillip mark']

• 数据量小、追求代码简洁：选直接遍历的方案，维护成本低
• 数据量大、对性能要求高：选按词组构建Trie的方案，性能优势明显

内容的提问来源于stack exchange，提问作者lefe