Trie, a prefix tree, is a tree-like data structure that organizes a collection of words by breaking each word down into its individual letters. Each path from the root to a leaf node represents a complete word, making it easy to locate specific words.
To find a word in the Trie, start at the root and follow the branches that correspond to the letters in the word. This allows you to quickly find the word you're looking for without searching through the entire structure. It's just like how we go to a library, where the books are organized by titles and subjects so that we can easily find what we need. Because of its efficiency in searching and storing vast collections of words, Trie data structure is used in various applications, including spell-checking and autocomplete.
Below, I summarized a list of Trie questions from Leetcode to help you better understand the topic. Happy coding!😄
https://leetcode.com/problems/implement-trie-prefix-tree/
class Node:
def __init__(self):
self.nxt = defaultdict(Node)
self.isWord = False
class Trie:
def __init__(self):
self.root = Node()
def insert(self, word: str) -> None:
cur = self.root
for c in word:
cur = cur.nxt[c]
cur.isWord = True
def search(self, word: str) -> bool:
cur = self.root
for c in word:
if c not in cur.nxt: return False
cur = cur.nxt[c]
return cur.isWord
def startsWith(self, prefix: str) -> bool:
cur = self.root
for c in prefix:
if c not in cur.nxt: return False
cur = cur.nxt[c]
return True
https://leetcode.com/problems/design-add-and-search-words-data-structure/
class Node:
def __init__(self):
self.nxt = defaultdict(Node)
self.isWord = False
class WordDictionary:
def __init__(self):
self.root = Node()
def addWord(self, word: str) -> None:
cur = self.root
for c in word:
cur = cur.nxt[c]
cur.isWord = True
def find(self, cur, u, word):
if u == len(word): return cur.isWord
if word[u] == ".":
for v in cur.nxt:
if self.find(cur.nxt[v], u + 1, word): return True
return False
else:
if word[u] not in cur.nxt: return False
return self.find(cur.nxt[word[u]], u + 1, word)
def search(self, word: str) -> bool:
return self.find(self.root, 0, word)
https://leetcode.com/problems/implement-magic-dictionary/
class Node:
def __init__(self):
self.nxt = defaultdict(Node)
self.isWord = False
class MagicDictionary:
def __init__(self):
self.root = Node()
def buildDict(self, dictionary: List[str]) -> None:
for s in dictionary:
cur = self.root
for c in s:
cur = cur.nxt[c]
cur.isWord = True
def find(self, s, cur, u, used):
if u == len(s):
return cur.isWord and used
for v in cur.nxt:
if s[u] == v:
if self.find(s, cur.nxt[v], u + 1, used): return True
else:
if not used and self.find(s, cur.nxt[v], u + 1, True): return True
return False
def search(self, searchWord: str) -> bool:
return self.find(searchWord, self.root, 0, False)
https://leetcode.com/problems/longest-common-prefix/
class Node:
def __init__(self):
self.nxt = defaultdict(Node)
self.cnt = 0
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
root = Node()
mx = 0
for s in strs:
cur = root
for i in range(len(s)):
cur = cur.nxt[s[i]]
cur.cnt += 1
if cur.cnt == len(strs):
mx = max(mx, i + 1)
return strs[0][:mx]