Created
July 26, 2023 01:09
-
-
Save omitakahiro/d30a397734b18aaea19b8ffd7649a4e3 to your computer and use it in GitHub Desktop.
(Naive) Python Implementation of Trie
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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