Search⌘ K
AI Features
Home
Courses
Grokking the Coding Interview Patterns

Solution: Implement Trie (Prefix Tree)

Understand how to implement a trie data structure with insert, search, and search prefix functions. Learn to efficiently manage strings for fast prefix matching and searching, key skills for coding interviews. This lesson guides you through creating trie nodes and handling operations with optimal time and space complexity.

We'll cover the following...

Statement

Trie is a tree-like data structure used to store strings. The tries are also called prefix trees because they provide very efficient prefix-matching operations. Implement a trie data structure with three functions that perform the following tasks:

  • Insert (word): This inserts a word into the trie.
  • Search (word): This searches the given word in the trie and returns TRUE, if found. Otherwise, return FALSE.
  • Search prefix (prefix): This searches the given prefix in the trie and returns TRUE, if found. Otherwise, return FALSE.

Constraints:

  • 1≤1 \leq word.length, prefix.length ≤500\leq 500
  • The strings consist only of lowercase English letters.
  • At most, 10310^3
...