208. Implement Trie (Prefix Tree)
Implement Trie (Prefix Tree) (LeetCode 208) is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Design Patterns pattern, in the Design (General/Specific) subpattern.
How to solve Implement Trie (Prefix Tree)
Implement Trie (Prefix Tree) is a Data Structure Design problem, part of Design Patterns. Design and implement data structures: LRU cache, LFU cache, HashMap, and specialized structures.
Work towards the solution in these steps:
- Consider using a tree-like data structure to represent prefixes of words efficiently, where each node corresponds to a character.
- Think about how each node can store links to child nodes representing subsequent characters, allowing traversal based on the input word or prefix.
- To support the search and insert operations, each node should be able to indicate whether it marks the end of a valid word inserted into the trie.
The reference solution runs in O(L) time and O(N * L) space.
The Implement Trie (Prefix Tree) solution and editorial walks through the full approach with reference code.
Problem statement
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 (i.e., 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.
Topics and companies
Topics: Hash Table, String, Design, Trie.
Reported in interviews at Amazon, Pinterest, Google, Microsoft, Oracle, Facebook, Apple, Goldman Sachs, Qualtrics.
How to practise Implement Trie (Prefix Tree) on Thita.ai
Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(L) time and O(N * L) space.
Open Implement Trie (Prefix Tree) in the code editor, or read the Implement Trie (Prefix Tree) editorial for a worked solution with its approach and complexity analysis.
Where Implement Trie (Prefix Tree) sits in the DSA pattern sheet
Problems related to Implement Trie (Prefix Tree)
Other problems that use the same Design (General/Specific) and Design Patterns techniques:
- Design Add and Search Words Data Structure — Medium, same subpattern
- Extra Characters in a String — Medium, same subpattern
- Longest Word in Dictionary — Easy, same subpattern
- Prefix and Suffix Search — Hard, same subpattern
- Replace Words — Medium, same subpattern
- Word Squares — Hard, same subpattern
Implement Trie (Prefix Tree) FAQ
What is the LeetCode number of Implement Trie (Prefix Tree)?
Implement Trie (Prefix Tree) is LeetCode problem 208, rated Medium.
What pattern is used to solve Implement Trie (Prefix Tree)?
Implement Trie (Prefix Tree) is a Data Structure Design problem. It belongs to the Design Patterns pattern, in the Design (General/Specific) subpattern.
What is the time complexity of Implement Trie (Prefix Tree)?
The reference solution runs in O(L) time and O(N * L) space.
Which companies ask Implement Trie (Prefix Tree)?
Implement Trie (Prefix Tree) has been reported in interviews at Amazon, Pinterest, Google, Microsoft, Oracle, Facebook, Apple, Goldman Sachs, Qualtrics.