![[python刷题模板] 字典树](http://www.mshxw.com/aiimages/31/932479.png "[python刷题模板] 字典树")
- 一、 算法&数据结构
- 1. 描述
- 2. 复杂度分析
- 3. 常见应用
- 4. 常用优化
- 二、 模板代码
- 1. 带.的模糊匹配
- 2. 前缀匹配
- `字典树`树实现
- `字典树`数组实现-动态开数组
- `字典树`数组实现-预先开数组
- 3. 最大异或和
- 三、其他
- 四、更多例题
- 五、参考链接
字典树通常用来处理字符串前缀查找问题，不过很多题都可以用cpp_map水过去2. 复杂度分析
在n个字符串words[i]里，执行m次查找
- 单次查询query, O(w),w为word长度
- 单次插入update，O(w)
- 建树，O(nw)
- 总查找，最坏O(nmw)，平均O(mw)
- 求前缀为s的字符串有多少
- 集合最大异或和
- 还有很多，我不会
- 树表示比较好写。
- 数组表示可以去查查CPP板子
例题: 211. 添加与搜索单词 - 数据结构设计
这题由于点代表任意字符，所以要dfs，写成了树
class TrieNode:
def __init__(self,cnt=0):
self.cnt = cnt
self.next = [None]*26
self.is_end = False
class WordDictionary:
def __init__(self):
self.root = TrieNode()
self.depth = 0
def addWord(self, word: str) -> None:
cur = self.root
for c in word:
i = ord(c)-ord('a')
if not cur.next[i] : # 没有这个字符
cur.next[i] = TrieNode()
cur = cur.next[i]
cur.cnt += 1
cur.is_end = True
def search(self, word: str) -> bool:
def dfs(root,word,start):
if not root:
return False
if start == len(word):
return root.is_end
c = word[start]
if c == '.':
for i in range(26):
if root.next[i] and root.next[i].cnt >0 and dfs(root.next[i],word,start+1):
return True
return False
else :
i = ord(c)-ord('a')
if not root.next[i] or root.next[i].cnt == 0:
return False
return dfs(root.next[i],word,start+1)
return dfs(self.root,word,0)
2. 前缀匹配
例题: 1268. 搜索推荐系统
字典树树实现经典案例
class TrieNode:
def __init__(self,cnt=0):
self.cnt = cnt
self.next = [None]*26
self.is_end = False
def insert(self, word: str) -> None:
cur = self
for c in word:
i = ord(c)-ord('a')
if not cur.next[i] : # 没有这个字符
cur.next[i] = TrieNode()
cur = cur.next[i]
cur.cnt += 1
cur.is_end = True
def find(self,word):
ans = []
cur = self
now_word=''
for c in word:
now_word+=c
i = ord(c)-ord('a')
if not cur.next[i]:
return ans
cur = cur.next[i]
def dfs(root,now_word):
if len(ans) >= 3:
return ans
if root.is_end:
ans.append(now_word)
for i in range(26):
c = chr(ord('a')+i)
if root.next[i]:
dfs(root.next[i],now_word+c)
dfs(cur,now_word)
return ans
class Solution:
def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:
trie = TrieNode()
for product in products:
trie.insert(product)
ans = []
for i in range(len(searchWord)):
ans.append(trie.find(searchWord[:i+1]))
return ans
字典树数组实现-动态开数组
提交后竟然没有树快
class Trie:
def __init__(self,c_cnt=26):
self.c_cnt=c_cnt
self.trie = [[0]*c_cnt]
self.is_end = [False]
self.w = [0] # 这个节点被经过了几次
def insert(self,word):
trie = self.trie
u = 0
for c in word:
i = ord(c)-ord('a')
if trie[u][i] == 0:
trie.append([0]*self.c_cnt)
trie[u][i] = len(trie)-1
self.is_end.append(False)
self.w.append(0)
u = trie[u][i]
self.w[u] += 1
self.is_end[u] = True
def find(self,word):
# 查找这个前缀的字符串有几个
trie = self.trie
u = 0
for c in word:
i = ord(c)-ord('a')
if trie[u][i] == 0:
return 0
u = trie[u][i]
return self.w[u]
def find_ans(self,word):
trie = self.trie
ans = []
u = 0
now_word=''
for c in word:
now_word+=c
i = ord(c)-ord('a')
if trie[u][i] == 0:
return ans
u = trie[u][i]
def dfs(u,now_word):
if len(ans) >= 3:
return ans
if self.is_end[u]:
ans.append(now_word)
for i in range(26):
c = chr(ord('a')+i)
if trie[u][i] > 0:
dfs(trie[u][i],now_word+c)
dfs(u,now_word)
return ans
class Solution:
def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:
trie = Trie()
for product in products:
trie.insert(product)
ans = []
for i in range(len(searchWord)):
ans.append(trie.find_ans(searchWord[:i+1]))
return ans
字典树数组实现-预先开数组
数组开辟长度应该=len*m,len是单词数，m是最长单词长度，提交后竟然没有动态开数组快
class Trie:
def __init__(self,size,c_cnt=26):
self.c_cnt=c_cnt
self.trie = [[0]*c_cnt for _ in range(size)]
self.is_end = [False] * (size)
self.w = [0] * (size) # 这个节点被经过了几次
self.total_cnt = 1
def insert(self,word):
trie = self.trie
u = 0
for c in word:
i = ord(c)-ord('a')
if trie[u][i] == 0:
trie[u][i] = self.total_cnt
self.total_cnt += 1
u = trie[u][i]
self.w[u] += 1
self.is_end[u] = True
def find(self,word):
# 查找这个前缀的字符串有几个
trie = self.trie
u = 0
for c in word:
i = ord(c)-ord('a')
if trie[u][i] == 0:
return 0
u = trie[u][i]
return self.w[u]
def find_ans(self,word):
trie = self.trie
ans = []
u = 0
now_word=''
for c in word:
now_word+=c
i = ord(c)-ord('a')
if trie[u][i] == 0:
return ans
u = trie[u][i]
def dfs(u,now_word):
if len(ans) >= 3:
return ans
if self.is_end[u]:
ans.append(now_word)
for i in range(26):
c = chr(ord('a')+i)
if trie[u][i] > 0:
dfs(trie[u][i],now_word+c)
dfs(u,now_word)
return ans
class Solution:
def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:
# ans.append(trie.find(searchWord[:i+1]))
max_len = max([len(s) for s in products])
trie = Trie(max_len*len(products)+1)
for product in products:
trie.insert(product)
ans = []
for i in range(len(searchWord)):
ans.append(trie.find_ans(searchWord[:i+1]))
return ans
3. 最大异或和
链接: 421. 数组中两个数的最大异或值
01字典树经典案例，贪心的去找子节点
class TrieNode:
def __init__(self,cnt=0):
self.cnt = cnt
self.next = [None]*2
self.is_end = False
def insert(self, a: int) -> None:
cur = self
for pos in range(31,-1,-1):
i = (a>>pos) & 1
if not cur.next[i] : # 没有这个字符
cur.next[i] = TrieNode()
cur = cur.next[i]
cur.cnt += 1
cur.is_end = True
def find(self,a):
ret = 0
cur = self
for pos in range(31,-1,-1):
i = (a>>pos) & 1
if i == 0:
if cur.next[1]:
cur = cur.next[1]
ret = ret*2+1
else:
cur = cur.next[0]
ret = ret*2
else:
if cur.next[0]:
cur = cur.next[0]
ret = ret*2+1
else:
cur = cur.next[1]
ret = ret*2
return ret
class Solution:
def findMaximumXOR(self, nums: List[int]) -> int:
trie = TrieNode()
# trie.insert(nums[0])
ans = -1e13
for num in nums:
trie.insert(num)
ans = max(ans,trie.find(num))
return ans
三、其他
- 字典树也有很多用法，但是我不太会：
1、前缀查询
2、最短前缀表示
3、删除字符串
4、删除前缀
5、集合前缀
6、离线算法
7、模糊匹配
8、集合最大异或
9、树的异或最长路。
- 1707. 与数组中元素的最大异或值，可以离线，套用第三题模板
- 链接: 夜深人静写算法（七）- 字典树
