You need to enable JavaScript to run this app. 如何查找两个字符串间的公共单词?空间优化及公共前缀场景处理
优惠活动
大模型
产品
解决方案
定价
更多

如何查找两个字符串间的公共单词?空间优化及公共前缀场景处理

双字符串公共单词查找的空间优化与公共前缀适配

基础实现的空间问题

常用的基础方案是把两个字符串全量分词后转集合求交集,空间复杂度为O(N+M)(N、M分别为两个字符串的单词总数),如果处理超大规模文本(比如GB级日志),会产生双倍冗余内存占用,完全没必要。

空间维度的优化方向

  • 小集合优先单存储:先统计两个字符串的分词结果数量,选单词数更少的那份转去重集合,遍历更长的那份的单词列表,每命中一次就记录公共单词,同时把这个单词从小集合中删除。这个方案把空间复杂度直接降到O(min(N,M)),还能自动避免长字符串中重复出现的同一个单词被多次统计。
  • 流式分词避免全量缓存:如果处理超大文本,不要一次性把字符串全拆成列表再转集合,改为按分隔符逐字符读取、边拼接单词边判断,内存里只需要存当前拼接的临时单词+小集合,不需要缓存整个分词列表,进一步压缩临时空间占用。
  • 低资源场景可选布隆过滤器:如果允许极小概率的误判(比如离线日志统计),可以用布隆过滤器替代哈希集合存储小集合的单词,空间占用是哈希集合的1/10甚至更低,命中时再做一次二次校验排除误判即可。

可以参考优化后的实现代码:

def get_common_words(str1: str, str2: str) -> list:
    words1 = str1.split()
    words2 = str2.split()
    # 确保小列表优先存储,省空间
    if len(words1) > len(words2):
        words1, words2 = words2, words1
    small_store = set(words1)
    common = []
    for word in words2:
        if word in small_store:
            common.append(word)
            small_store.remove(word)
    return common

带公共前缀的单词场景适配

当两个字符串里的单词存在大量公共前缀(比如大量h开头、hi开头的单词),原有的哈希集合存储方案会重复存储相同前缀的字符,此时可以改用**小集合构建前缀树(Trie)**适配:

  • 空间层面:公共前缀部分在Trie中仅存储一次,比如100个以h开头、50个以hi开头的单词,Trie只会存1次根节点下的h、hi公共节点,比哈希集合每个单词单独存储完整字符串的空间占用更低。
  • 匹配层面:遍历长字符串的单词时,逐字符在Trie中向下走,如果中途遇到无匹配的分支可以直接终止当前单词的判断,不需要读完整个单词,比哈希集合需要计算整个单词的哈希值再判断效率更高。

简单的Trie实现参考:

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False
def build_trie(words: list) -> TrieNode:
    root = TrieNode()
    for word in words:
        cur = root
        for c in word:
            if c not in cur.children:
                cur.children[c] = TrieNode()
            cur = cur.children[c]
        cur.is_end = True
    return root
def query_and_remove(root: TrieNode, word: str) -> bool:
    cur = root
    path = []
    for c in word:
        if c not in cur.children:
            return False
        path.append(cur)
        cur = cur.children[c]
    if cur.is_end:
        cur.is_end = False # 命中后标记删除,避免重复统计
        # 可额外清理无后续子节点的空路径节点,进一步省空间
        for i in range(len(path)-1, -1, -1):
            parent = path[i]
            child_c = word[i]
            if not parent.children[child_c].children:
                del parent.children[child_c]
        return True
    return False

使用时只需要把之前的small_store = set(words1)替换成small_store = build_trie(words1),把word in small_store的判断替换成query_and_remove(small_store, word)即可,完全适配原有逻辑的同时,兼容公共前缀的单词场景。

内容的提问来源于stack exchange,提问作者Xabnord

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.11.21 15:45:02