LeetCode 前缀树应用场景题解

LeetCode 前缀树应用场景题解

题目描述

总结前缀树的各种应用场景。

前缀树的应用场景

1. 自动补全

• 输入框自动补全，根据用户输入的前缀返回可能的完整字符串。

2. 搜索引擎

• 搜索引擎的搜索建议，根据用户输入的前缀返回搜索建议。

3. IP路由

• 在网络中查找最长前缀匹配，用于 IP 路由。

4. 字符串分类

• 将字符串按照前缀进行分类。

5. 词频统计

• 统计字符串出现的频率。

6. 字符串搜索

• 在文本中搜索模式串的出现位置。

7. 最大异或值

• 找出数组中两个元素的最大异或值。

代码实现

class TrieNode: def __init__(self): self.children = {} self.is_end = False self.count = 0 class Trie: def __init__(self): self.root = TrieNode() def insert(self, word): node = self.root for char in word: if char not in node.children: node.children[char] = TrieNode() node = node.children[char] node.count += 1 node.is_end = True def search(self, word): node = self.root for char in word: if char not in node.children: return None node = node.children[char] return node.count def startsWith(self, prefix): node = self.root for char in prefix: if char not in node.children: return 0 node = node.children[char] return node.count # 测试 def test_trie(): trie = Trie() trie.insert("apple") trie.insert("app") print(trie.search("app")) # 输出：1 print(trie.startsWith("ap")) # 输出：2 if __name__ == "__main__": test_trie()

总结

前缀树是一种高效的数据结构，适用于处理字符串前缀相关的各种问题。