如何高效去除字符串列表中的重复项及子字符串（保留较长串）

给定包含重复项和子/父域名的Python字符串列表，我们需要去除重复项，并优先保留更长的域名（比如保留www.google.com而非google.com）。以下是两种实现方案：

方案一：排序+筛选（适合中小规模列表） #

这个方法逻辑简单，容易理解，处理普通规模的域名列表足够高效：

a = [
    'www.google.com',
    'google.com',
    'tvi.pt',
    'ubs.ch',
    'google.it',
    'www.google.com'
]

# 1. 去重并保留原顺序（Python 3.7+ 字典默认有序）
unique_domains = list(dict.fromkeys(a))
# 2. 按字符串长度降序排序，让长域名优先被处理
sorted_domains = sorted(unique_domains, key=lambda x: -len(x))
# 3. 筛选：只保留未被结果列表中已有域名包含的项
result = []
for domain in sorted_domains:
    if not any(domain in item for item in result):
        result.append(domain)

print(result)
# 输出: ['www.google.com', 'tvi.pt', 'ubs.ch', 'google.it']

逻辑说明： #

• 用dict.fromkeys(a)去重，既能去除重复项，又能保留原列表的相对插入顺序（Python 3.7+有效）。
• 按长度降序排序是核心：长域名先被加入结果列表，后续短域名如果是已有长域名的子串，会直接被过滤。
• 遍历检查时，any(domain in item for item in result)快速判断当前域名是否是结果中某一域名的子串，避免保留冗余的短域名。

方案二：Trie树（字典树）实现（适合大规模域名列表） #

如果需要处理百万级以上的海量域名，Trie树的时间复杂度更优（O(总字符数)），能大幅提升效率：

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False
        self.domain = None

def build_trie(domains):
    root = TrieNode()
    for domain in domains:
        # 将域名按`.`拆分后反转，从顶级域开始构建Trie
        reversed_parts = domain.split('.')[::-1]
        node = root
        for part in reversed_parts:
            if part not in node.children:
                node.children[part] = TrieNode()
            node = node.children[part]
        node.is_end = True
        node.domain = domain
    return root

def get_longest_domains(root):
    result = []
    def traverse(node):
        # 遇到域名结尾节点时，直接保留并停止向下遍历（子节点对应更短的父域，无需保留）
        if node.is_end:
            result.append(node.domain)
            return
        for child in node.children.values():
            traverse(child)
    traverse(root)
    return result

# 使用示例
a = [
    'www.google.com',
    'google.com',
    'tvi.pt',
    'ubs.ch',
    'google.it',
    'www.google.com'
]

# 先去重
unique_domains = list(set(a))
# 构建Trie树并获取结果
root = build_trie(unique_domains)
result = get_longest_domains(root)
print(result)
# 输出（顺序可能不同）: ['www.google.com', 'tvi.pt', 'ubs.ch', 'google.it']

逻辑说明： #

• 反转域名后构建Trie，让父域（短域名）成为子域（长域名）的上层节点。
• 遍历Trie时，只要遇到标记为域名结尾的节点，就保留该域名并停止向下遍历——这样就能自动跳过所有属于该域名的父域短域名，确保只保留最长的完整域名。

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