Authored by Tony Feng
Created on April 10th, 2022
Last Modified on April 10th, 2022
Understanding Trie
Main Concepts
- A trie is a special tree that can compactly store strings.
- Tries are based on the prefix of a string.
- They are used to represent the “Retrieval” of data and thus the name Trie.
Charateristics
- Strengths
- Sometimes Space-Efficient. If you’re storing lots of words that start with similar patterns, tries may reduce the overall storage cost by storing shared prefixes once.
- Efficient Prefix Queries. Tries can quickly answer queries about words with shared prefixes
- Weakness
- Usually Space-Inefficient. Tries rarely save space when compared to storing strings in a set.
- Not Standard. Most languages don’t come with a built-in trie implementation.
Example
Leetcode 208 Implement Trie (Prefix Tree)
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
30
31
32
33
34
35
36
37
38
39
40
41
|
class TrieNode:
def __init__(self, char = ""):
self.char = char
self.children = {}
self.is_end = False
# self.counter = 0
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word: str) -> None:
node = self.root
for char in word:
if char in node.children:
node = node.children[char]
else:
new_node = TrieNode(char)
node.children[char] = new_node
node = new_node
node.is_end = True
# node.counter += 1
def search(self, word: str) -> bool:
node = self.root
for char in word:
if char not in node.children:
return False
node = node.children[char]
# Reached at the end of word
# return True if word is present, i.e is_end = True else False
return node.is_end
def startsWith(self, prefix: str) -> bool:
node = self.root
for char in prefix:
if char not in node.children:
return False
node = node.children[char]
return True
|
Leetcode 720 Longest Word in Dictionary
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
|
class TrieNode:
def __init__(self, val):
self.children = {}
self.value = val
self.endOfWord = False
class Solution:
def longestWord(self, words: List[str]) -> str:
root = TrieNode(0)
maxLen = 0
res = ""
for word in sorted(words):
cur = root
count = 0
for letter in word:
if letter not in cur.children:
cur.children[letter] = TrieNode(count)
cur = cur.children[letter]
if cur.endOfWord: count += 1
cur.endOfWord = True
cur.value += 1
if cur.value == len(word) and cur.value > maxLen:
maxLen = cur.value
res = word
return res
|
Reference