leetcode/208-240525-pass/main1.py
2024-05-26 18:55:13 +02:00

42 lines
1.5 KiB
Python

class TrieNode:
def __init__(self, val = ''):
self.child = []
self.is_word = False
self.val = val
self.child_map = {}
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word: str) -> None:
parent_node = self.root
for idx, letter in enumerate(word):
if letter not in parent_node.child_map:
new_node = TrieNode(letter)
parent_node.child.append(new_node)
parent_node.child_map[letter] = len(parent_node.child) - 1
parent_node = new_node
else:
idx = parent_node.child_map[letter]
parent_node = parent_node.child[idx]
parent_node.is_word = True
def search(self, word: str) -> bool:
parent_node = self.root
for idx, letter in enumerate(word):
if letter not in parent_node.child_map:
return False
idx = parent_node.child_map[letter]
parent_node = parent_node.child[idx]
if parent_node.is_word == False:
return False
return True
def startsWith(self, prefix: str) -> bool:
parent_node = self.root
for idx, letter in enumerate(prefix):
if letter not in parent_node.child_map:
return False
idx = parent_node.child_map[letter]
parent_node = parent_node.child[idx]
return True