Design a Trie

Implement a trie (prefix tree) data structure to efficiently store and retrieve words. This problem tests your understanding of tree-based structures and their application to string manipulation, a common theme in coding interviews.

trieprefix treestringdata structuretree

Problem Statement

Design a data structure that supports the following operations on a set of strings: adding a new string to the set, checking if a given string is present in the set, and determining if there are any strings in the set that start with a given prefix. The data structure should be optimized for prefix-based searches.

Example 1

Input: (add('mars'), add('map'), has_prefix('ma'), search('map'), search('maze'), add('maze'), search('maze'))

Output: (True, True, False, True)

Initially, the trie is empty. After adding 'mars' and 'map', the prefix 'ma' exists. 'map' is found, 'maze' isn't. After adding 'maze', 'maze' is found.

Example 2

Input: (add('cat'), add('car'), add('can'), search('ca'), has_prefix('ca'), search('car'), has_prefix('co'))

Output: (False, True, True, False)

After adding 'cat', 'car', and 'can', the string 'ca' is not present, but the prefix 'ca' exists. 'car' is present, but the prefix 'co' is not.

Constraints

-All words consist of lowercase English letters.
-The length of each word is between 1 and 200 characters.
-The number of calls to add, search, and has_prefix will not exceed 10000.
-The prefix length is between 1 and 200 characters.

Brute Force Approach

The brute force approach would involve storing all the words in a list. To search for a word, you'd iterate through the list and compare each word. To find a prefix, you'd iterate through the list and check if each word starts with the given prefix. Imagine searching a physical dictionary by flipping through every page to find a word or prefix - that's the brute force way. This is highly inefficient.

TimeO(n*m)

SpaceO(n*m)

Ready to practice?

Work through this problem with AI coaching and get real-time feedback

Practice This Problem