Exercise: Trie Problems on LeetCode

labuladongOriginalAbout 1288 words

This article will resolve

LeetCode	Difficulty
1804. Implement Trie II (Prefix Tree)🔒	🟠
208. Implement Trie (Prefix Tree)	🟠
211. Design Add and Search Words Data Structure	🟠
648. Replace Words	🟠
677. Map Sum Pairs	🟠

Prerequisites

Before reading this article, you need to learn:

With TrieMap and TrieSet, all prefix tree-related problems on LeetCode can be directly applied. Below, I will illustrate with a few examples.

Possible Optimizations

First, the TrieMap/TrieSet implementation provided in the previous article Implementation of TrieMap/TrieSet certainly has room for optimization in specific problems.

For example, in LeetCode problems related to prefix trees, the input is restricted to lowercase English letters a-z. Therefore, TrieNode does not need to maintain a children array of size 256; setting the size to 26 is sufficient, which can reduce time and space complexity.

Additionally, the previously provided Java/C++ code includes generics, which are not needed when solving algorithm problems. Removing generics can also provide some efficiency improvements.

208. Implement Trie (Prefix Tree)

Let's look at LeetCode Problem 208 "Implement Trie (Prefix Tree)":

208. Implement Trie (Prefix Tree) | LeetCode | 🟠

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⁴ calls in total will be made to insert, search, and startsWith.

The problem is from LeetCode 208. Implement Trie (Prefix Tree).

The functions that the problem asks us to implement are actually part of the TrieSet API, so directly encapsulating a TrieSet can solve this problem.

Exercise: Trie Problems on LeetCode

208. Implement Trie (Prefix Tree)

648. Replace Words

211. Add and Search Word - Data Structure Design

1804. Implement a Trie (Prefix Tree II)

677. Map Sum Pairs