Skip to content

Instantly share code, notes, and snippets.

@cashlo
Created August 1, 2018 19:34
Show Gist options
  • Save cashlo/a5ae81068fad78fec14289734b1a931f to your computer and use it in GitHub Desktop.
Save cashlo/a5ae81068fad78fec14289734b1a931f to your computer and use it in GitHub Desktop.
class Trie(object):
def __init__(self):
"""
Initialize your data structure here.
"""
self.char_map = {}
def insert(self, word):
"""
Inserts a word into the trie.
:type word: str
:rtype: void
"""
if not word:
self.char_map[''] = None
return
if word[0] not in self.char_map:
self.char_map[word[0]] = Trie()
self.char_map[word[0]].insert(word[1:])
def search(self, word):
"""
Returns if the word is in the trie.
:type word: str
:rtype: bool
"""
# print 'searching: {}'.format(word)
if not word: return '' in self.char_map
if word[0] in self.char_map:
if self.char_map[word[0]] is None: return False
return self.char_map[word[0]].search(word[1:])
return False
def startsWith(self, prefix):
"""
Returns if there is any word in the trie that starts with the given prefix.
:type prefix: str
:rtype: bool
"""
# print 'startsWith: {}'.format(prefix)
if prefix[0] in self.char_map:
if len(prefix) == 1:
return True
if self.char_map[prefix[0]] is None: return False
return self.char_map[prefix[0]].startsWith(prefix[1:])
return False
# Your Trie object will be instantiated and called as such:
# obj = Trie()
# obj.insert(word)
# param_2 = obj.search(word)
# param_3 = obj.startsWith(prefix)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment