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

Solution: Implement Trie (Prefix Tree)

Understand how to implement a trie, a tree-like data structure optimized for string storage and prefix matching. This lesson teaches you to build insert, search, and prefix search operations, improving your ability to handle string-related coding interview problems efficiently.

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
...