相关集合
- 书 https://leetcode-cn.com/leetbook/detail/trie/
- 题 https://leetcode-cn.com/tag/trie/problemset/
一些必背题
676. Implement Magic Dictionary
!!! 典型题
用dfs似乎更好写一些
class TrieNode:
def __init__(self):
self.children = dict()
self.is_word = False
class MagicDictionary:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
curr = self.root
for char in word:
if char not in curr.children:
curr.children[char] = TrieNode()
curr = curr.children[char]
curr.is_word = True
def buildDict(self, dictionary) -> None:
for word in dictionary:
self.insert(word)
def search(self, searchWord: str) -> bool:
res = [False]
def dfs(node, idx, flit):
if res[0]:
return
if idx == len(searchWord):
if flit == 1 and node.is_word:
res[0] = True
return
for child in node.children:
if searchWord[idx] == child:
dfs(node.children[child], idx + 1, flit)
else:
if flit == 0:
dfs(node.children[child], idx + 1, 1)
dfs(self.root, 0, 0)
return res[0]
820. Short Encoding of Words
题目很有趣，字典可以压缩
题很简单，比其它中等简单很多
class TrieNode:
def __init__(self):
self.children = dict()
self.is_word = False
class Solution:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
curr = self.root
for char in word:
if not char in curr.children:
curr.children[char] = TrieNode()
curr = curr.children[char]
curr.is_word = True
def minimumLengthEncoding(self, words) -> int:
for word in words:
self.insert(word[::-1])
res = [0]
def dfs(node, level):
if not node.children:
res[0] += level
for child_node in node.children.values():
dfs(child_node, level + 1)
dfs(self.root, 1)
return res[0]
题目
677. Map Sum Pairs
import collections
class TrieNode:
def __init__(self):
self.children = collections.defaultdict(TrieNode)
self.val = 0
class MapSum:
def __init__(self):
self.root = TrieNode()
def insert(self, key: str, val: int) -> None:
curr = self.root
for char in key:
curr=curr.children[char]
curr.val=val
def sum(self, prefix: str) -> int:
curr=self.root
for char in prefix:
curr=curr.children[char]
if curr is None:
return 0
res=0
queue=[curr]
while queue:
new_queue=[]
for item in queue:
new_queue.extend(item.children.values())
res+=item.val
queue=new_queue
return res
648. Replace Words
在模版上改一改
import collections
class TrieNode:
def __init__(self):
# 如果字符是有限的，这里可以用 list 来存储。不用做hash更快
self.children = collections.defaultdict(TrieNode)
self.is_word = False
self.whole_word=None
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word: str) -> None:
curr = self.root
for char in word:
curr = curr.children[char]
# 要求只记录最短的，长的就不往里面塞了
if curr.is_word:
return
curr.is_word = True
curr.whole_word=word
def search(self, word: str) -> bool:
curr = self.root
for char in word:
curr = curr.children.get(char)
if curr is None:
return False
return curr.is_word
def startsWith(self, prefix: str) -> bool:
curr = self.root
for char in prefix:
curr = curr.children.get(char)
if curr is None:
return False
return True
def in_start(self, sentence):
curr = self.root
for char in sentence:
if char not in curr.children:
return False
curr = curr.children.get(char)
if curr.is_word:
return True
return False
def extract_prefix(self,sentence):
curr = self.root
for char in sentence:
if char not in curr.children:
return sentence
curr = curr.children.get(char)
if curr.is_word:
return curr.whole_word
return sentence
class Solution:
def replaceWords(self, dictionary: List[str], sentence: str) -> str:
trie=Trie()
for word in dictionary:
trie.insert(word)
res=[]
for s in sentence.split(' '):
res.append(trie.extract_prefix(s))
return ' '.join(res)
211. Design Add and Search Words Data Structure
BFS
class TrieNode:
def __init__(self):
self.children = dict()
self.is_word = False
def __repr__(self):
return str(self.children.keys())
class WordDictionary:
def __init__(self):
self.root = TrieNode()
def addWord(self, word: str) -> None:
curr = self.root
for char in word:
if char not in curr.children:
curr.children[char] = TrieNode()
curr = curr.children[char]
curr.is_word = True
def search(self, word: str) -> bool:
queue, idx = [self.root], 0
while queue and idx < len(word):
new_queue = []
if word[idx] == '.':
for curr in queue:
new_queue.extend(curr.children.values())
else:
for curr in queue:
if word[idx] in curr.children:
new_queue.append(curr.children[word[idx]])
if not new_queue:
return False
queue = new_queue
idx += 1
if idx < len(word):
return False
for curr in queue:
if curr.is_word:
return True
return False
dfs版本，不过效率低于 BFS
class TrieNode:
def __init__(self):
self.children = dict()
self.is_word = False
class WordDictionary:
def __init__(self):
self.root = TrieNode()
def addWord(self, word: str) -> None:
curr = self.root
for char in word:
if char not in curr.children:
curr.children[char] = TrieNode()
curr = curr.children[char]
curr.is_word = True
def search(self, word: str) -> bool:
res = [False]
def dfs(node, idx):
if res[0]:
return
if idx == len(word):
if node.is_word:
res[0] = True
return
if word[idx] == '.':
for child in node.children.values():
dfs(child, idx + 1)
else:
if word[idx] in node.children:
dfs(node.children[word[idx]], idx + 1)
dfs(self.root, 0)
return res[0]
386. Lexicographical Numbers
class Solution:
def lexicalOrder(self, n: int) -> List[int]:
tmp=[str(i) for i in range(1,n+1)]
tmp.sort()
return [int(i) for i in tmp]
720
class TrieNode:
def __init__(self):
self.children=dict()
self.is_word=False
class Solution:
def __init__(self):
self.root=TrieNode()
def insert(self,word):
curr=self.root
for char in word:
if char not in curr.children:
curr.children[char]=TrieNode()
curr=curr.children[char]
curr.is_word=True
def add_dictionary(self,words):
for word in words:
self.insert(word)
def longestWord(self, words: List[str]) -> str:
self.add_dictionary(words)
res=['']
def dfs(node,string):
#print(string)
if node.is_word:
if len(string)==len(res[0]):
res.append(string)
elif len(string)>len(res[0]):
res.clear()
res.append(string)
for child_char,child_node in node.children.items():
if child_node.is_word:
dfs(child_node,string+child_char)
dfs(self.root,'')
res.sort()
return res[0]
745
作弊：先暴力把所有情况列出来
class WordFilter:
def __init__(self, words: List[str]):
self.dictionary=dict()
for idx,word in enumerate(words):
for i in range(1,len(word)+1):
p=word[:i]
for j in range(len(word)):
q=word[j:]
self.dictionary[(p,q)]=idx
def f(self, prefix: str, suffix: str) -> int:
if (prefix,suffix) in self.dictionary:
return self.dictionary[(prefix,suffix)]
return -1
# Your WordFilter object will be instantiated and called as such:
# obj = WordFilter(words)
# param_1 = obj.f(prefix,suffix)
1233. Remove Sub-Folders from the Filesystem
class TrieNode:
def __init__(self):
self.children=dict()
self.is_word=False
class Solution:
def __init__(self):
self.root=TrieNode()
def insert(self,word):
curr=self.root
for char in word.split('/')[1:]:
if char not in curr.children:
curr.children[char]=TrieNode()
curr=curr.children[char]
curr.is_word=True
def removeSubfolders(self, folder: List[str]) -> List[str]:
for word in folder:
self.insert(word)
res=[]
def dfs(node,string):
if node.is_word:
res.append(string)
return
for child_char,child_node in node.children.items():
dfs(child_node,string+'/'+child_char)
dfs(self.root,'')
return res
用不到 Trie
692. Top K Frequent Words
import collections
class Solution:
def topKFrequent(self, words: List[str], k: int) -> List[str]:
words.sort()
return [i[0] for i in collections.Counter(words).most_common(k)]
1023. Camelcase Matching
用正则
import re
class Solution:
def camelMatch(self, queries: List[str], pattern: str) -> List[bool]:
pattern_str='[a-z]*?'
for char in pattern:
pattern_str+=(char+'[a-z]*?')
regex=re.compile(pattern_str)
return [bool(regex.fullmatch(q)) for q in queries]
1268. Search Suggestions System
有重复的，因此用 Trie 反而麻烦了
class Solution:
def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:
max_cnt=3
products.sort()
res=[]
for idx in range(1,len(searchWord)+1):
searchWord_tmp=searchWord[:idx]
cnt=0
res_tmp=[]
for product in products:
if product.startswith(searchWord_tmp):
res_tmp.append(product)
cnt+=1
if cnt==3:
break
res.append(res_tmp)
return res
745
作弊：先暴力把所有情况列出来
class WordFilter:
def __init__(self, words: List[str]):
self.dictionary=dict()
for idx,word in enumerate(words):
for i in range(1,len(word)+1):
p=word[:i]
for j in range(len(word)):
q=word[j:]
self.dictionary[(p,q)]=idx
def f(self, prefix: str, suffix: str) -> int:
if (prefix,suffix) in self.dictionary:
return self.dictionary[(prefix,suffix)]
return -1
