Skip to content

Instantly share code, notes, and snippets.

@omitakahiro
Created July 26, 2023 01:09
Show Gist options
  • Save omitakahiro/d30a397734b18aaea19b8ffd7649a4e3 to your computer and use it in GitHub Desktop.
Save omitakahiro/d30a397734b18aaea19b8ffd7649a4e3 to your computer and use it in GitHub Desktop.
(Naive) Python Implementation of Trie
from __future__ import annotations
class TrieNode:
def __init__(self, char: str):
self.char = char
self.is_end = False
self.children = {}
def add_child(self, char: str) -> None:
if char not in self.children:
self.children[char] = TrieNode(char)
def get_child(self, char: str) -> Union[TrieNode, None]:
return self.children.get(char, None)
def end(self) -> None:
self.is_end = True
class Trie:
def __init__(self):
self.root = TrieNode("")
def add(self, keyword: str):
if keyword:
node = self.root
for char in list(keyword):
node.add_child(char)
node = node.get_child(char)
node.end()
def query(self, text: str) -> list[str]:
keyword_matched = []
for i in range(len(text)):
node = self.root
text_sub = text[i:]
for j, char in enumerate(text_sub):
node = node.get_child(char)
if node is None:
break
elif node.is_end:
keyword_matched.append(text_sub[:j+1])
return keyword_matched
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment