Skip to content

Instantly share code, notes, and snippets.

@itissid
Created July 26, 2018 17:12
Show Gist options
  • Save itissid/6a5bec95424b5630908e877c02d957d5 to your computer and use it in GitHub Desktop.
Save itissid/6a5bec95424b5630908e877c02d957d5 to your computer and use it in GitHub Desktop.
A simple Trie implementation
class Trie:
def __init__(self):
"""
Initialize your data structure here.
"""
self.root_dict = {}
def insert(self, word):
"""
Inserts a word into the trie.
:type word: str
:rtype: void
"""
root = self.root_dict
for s in word:
if s not in root:
root[s] = {}
root = root[s]
root['$'] = True
def _search_prefix_helper(self, word):
"""
Given a word returns False if the word is not a prefix of current wordlist or
it returns the root dictionary for the last letter of word found in the trie or it returns None if the prefix
"""
root = self.root_dict
for s in word:
if s not in root:
return None
root = root[s]
return root
def search(self, word):
"""
Returns if the word is in the trie.
:type word: str
:rtype: bool
"""
root = self._search_prefix_helper(word)
return root is not None and '$' in root
def startsWith(self, prefix):
"""
Returns if there is any word in the trie that starts with the given prefix.
:type prefix: str
:rtype: bool
"""
root = self._search_prefix_helper(prefix)
return root is not None
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment