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

Solution: Implement Trie (Prefix Tree)

Explore how to implement a trie data structure to efficiently store and search strings. Understand the insert, search, and prefix search operations, their time and space complexities, and how tries provide fast prefix-matching capabilities.

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