字典树 | 笔记整理!

字典树 | 笔记整理!

字典树

实现 | 数组 + 字典(哈希表)

208.实现 Trie (前缀树)

数组存储

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Trie():
def __init__(self) -> None:
self.d=[0]*26
self.flag=False

def insert(self,words):
node=self
for i in words:
i=ord(i)-ord('a')
if node.d[i]==0:
node.d[i]=Trie()
node=node.d[i]
node.flag=True

def search(self,words):
node=self.search_prefix(words)
return node!=None and node.flag

def search_prefix(self,words):
node=self
for i in words:
i=ord(i)-ord('a')
if node.d[i]==0:
return None
node=node.d[i]
return node

def startsWith(self,words):
return self.search_prefix(words)!=None

哈希表(字典)存储

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Trie:
def __init__(self):
self.d=defaultdict(int)
self.tag=False

def insert(self, word: str) -> None:
node=self
for i in word:
v=ord(i)-ord('a')
if not node.d[v]:
node.d[v]=Trie()
node=node.d[v]
node.tag=True

def search_prefix(self, word: str) -> bool:
node=self
for i in word:
v=ord(i)-ord('a')
if not node.d[v]:
return None
node=node.d[v]
return node

def search(self,word):
node=self.search_prefix(word)
return node is not None and node.tag

def startsWith(self, prefix: str) -> bool:
return self.search_prefix(prefix) is not None

应用

判断前缀和

14. 最长公共前缀

暴力 | 强行操作即可

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
def helper(x,y):
i=0
while i<len(x) and i<len(y) and x[i]==y[i]:
i+=1
return x[:i]
n=len(strs)
ans=strs[0]
for i in range(1,n):
ans=helper(ans,strs[i])
return ans

分治 | 参考归并排序 (合并k个链表)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
### 分治思想
def helper(l,r):
if l>=r:
return strs[l]
mid=l+r>>1
l=helper(l,mid)
r=helper(mid+1,r)
k=min(len(l),len(r))
for i in range(k):
if l[i]!=r[i]:
k=i
break
return l[:k]
return helper(0,len(strs)-1)

前缀树 | 存储 字符即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Trie:
def __init__(self):
self.d=defaultdict(int)
self.tag=False
def insert(self, word: str) -> None:
node=self
for v in word:
if not node.d[v]:
node.d[v]=Trie()
node=node.d[v]
node.tag=True
def search(self, word: str) -> bool:
node=self
ans=''
for v in word:
### 遇到分治或是到达低端 就判断即可!
if len(node.d)>1 or node.tag:
return ans
if v in node.d:
ans+=v
node=node.d[v]
return ans
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
t=Trie()
for i in strs:t.insert(i)
return t.search(strs[0])