[Leetcode] 0208. Implement Trie

/ Leetcode, Technical Article / By

Explore diverse LeetCode solutions in Python, C++, JavaScript, SQL, and TypeScript. Ideal for interview prep, learning, and code practice in multiple programming languages. Github Repo Link

A trie (pronounced as “try”) or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker.

Implement the Trie class:

  • Trie() Initializes the trie object.
  • void insert(String word) Inserts the string word into the trie.
  • boolean search(String word) Returns true if the string word is in the trie (ie, was inserted before), and false otherwise.
  • boolean startsWith(String prefix) Returns true if there is a previously inserted string word that has the prefix prefix, and false otherwise.

 

Example 1:

Input
["Trie", "insert", "search", "search", "startsWith", "insert", "search"] [[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
Output
[null, null, true, false, true, null, true]

Explanation
Trie trie = new Trie(); trie.insert("apple"); trie.search("apple"); // return True trie.search("app"); // return False trie.startsWith("app"); // return True trie.insert("app"); trie.search("app"); // return True

 

Constraints:

  • 1 <= word.length, prefix.length <= 2000
  • word and prefix consist only of lowercase English letters.
  • At most 3 * 10 4 calls in total will be made to insert, search, and startsWith.

Table of contents

Python

				
					# insert() # time complexity: O(l) # space complexity: O(l) # search() # time complexity: O(l) # space complexity: O(1) # search prefix() # time complexity: O(l) # space complexity: O(1) class TrieNode: def __init__(self, char: str = ""): self.char = char self.children = {} self.isEnd = False class Trie: def __init__(self): self.root = TrieNode() def insert(self, word: str): node = self.root for c in word: if c in node.children: node = node.children[c] else: newNode = TrieNode() node.children[c] = newNode node = newNode node.isEnd = True def search(self, word: str): node = self.root for c in word: if c not in node.children: return False node = node.children[c] return node.isEnd def startsWith(self, prefix: str): node = self.root for c in prefix: if c not in node.children: return False node = node.children[c] return True # Your Trie object will be instantiated and called as such: trie = Trie() trie.insert("apple") print(trie.search("apple")) print(trie.search("app")) print(trie.startsWith("app")) trie.insert("app") print(trie.search("app"))

related articles