如何查找两个字符串间的公共单词?空间优化及公共前缀场景处理
双字符串公共单词查找的空间优化与公共前缀适配
基础实现的空间问题
常用的基础方案是把两个字符串全量分词后转集合求交集,空间复杂度为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
相关产品推荐
相关产品推荐

