May-14 2020 Challenge

Implement Trie (Prifix Tree)

Implement a trie with insert, search, and startsWith methods.

Example:

Trie trie = new Trie();

trie.insert("apple");
trie.search("apple");   // returns true
trie.search("app");     // returns false
trie.startsWith("app"); // returns true
trie.insert("app");   
trie.search("app");     // returns true

Note:

• You may assume that all inputs are consist of lowercase letters a-z.
• All inputs are guaranteed to be non-empty strings.

Solution in python:

class Trie(object):

   def __init__(self):

      self.child = {}

   def insert(self, word):

      current = self.child

      for l in word:

         if l not in current:

            current[l] = {}

         current = current[l]

      current['#']=1

   def search(self, word):

      current = self.child

      for l in word:

         if l not in current:

            return False

         current = current[l]

      return '#' in current

   def startsWith(self, prefix):

      current = self.child

      for l in prefix:

         if l not in current:

            return False

         current = current[l]

      return True

ob1 = Trie()

ob1.insert("apple")

print(ob1.search("apple"))

print(ob1.search("app"))

print(ob1.startsWith("app"))

ob1.insert("app")

print(ob1.search("app"))

leetcode graph leetcode google leetcode group anagrams leetcode github leetcode google interview questions lis 

leetcode google interview leetcode greedy leetcode gas station leetcode house robber leetcode happy number leetcode hashmap leetcode help center leetcode heap leetcode hard problems leetcode history

leetcode happy number solution leetcode ide leetcode interview questions leetcode internship leetcode island perimeter leetcode india leetcode intersection of two linked lists leetcode implement trie leetcode interview experience leetcode java leetcode javascript leetcode jump game leetcode java solutions leetcode jump game ii leetcode javascript solutions leetcode java questions leetcode jobs leetcode knapsack leetcode knapsack problem leetcode kth smallest element leetcode kmp leetcode k closest points leetcode kth smallest element in a bst leetcode kadane leetcode keys and rooms