Created
July 26, 2018 17:12
-
-
Save itissid/6a5bec95424b5630908e877c02d957d5 to your computer and use it in GitHub Desktop.
A simple Trie implementation
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
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