1804. Implement Trie II (Prefix Tree) π
Description
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 stringword
into the trie.int countWordsEqualTo(String word)
Returns the number of instances of the stringword
in the trie.int countWordsStartingWith(String prefix)
Returns the number of strings in the trie that have the stringprefix
as a prefix.void erase(String word)
Erases the stringword
from the trie.
Example 1:
Input ["Trie", "insert", "insert", "countWordsEqualTo", "countWordsStartingWith", "erase", "countWordsEqualTo", "countWordsStartingWith", "erase", "countWordsStartingWith"] [[], ["apple"], ["apple"], ["apple"], ["app"], ["apple"], ["apple"], ["app"], ["apple"], ["app"]] Output [null, null, null, 2, 2, null, 1, 1, null, 0] Explanation Trie trie = new Trie(); trie.insert("apple"); // Inserts "apple". trie.insert("apple"); // Inserts another "apple". trie.countWordsEqualTo("apple"); // There are two instances of "apple" so return 2. trie.countWordsStartingWith("app"); // "app" is a prefix of "apple" so return 2. trie.erase("apple"); // Erases one "apple". trie.countWordsEqualTo("apple"); // Now there is only one instance of "apple" so return 1. trie.countWordsStartingWith("app"); // return 1 trie.erase("apple"); // Erases "apple". Now the trie is empty. trie.countWordsStartingWith("app"); // return 0
Constraints:
1 <= word.length, prefix.length <= 2000
word
andprefix
consist only of lowercase English letters.- At most
3 * 104
calls in total will be made toinsert
,countWordsEqualTo
,countWordsStartingWith
, anderase
. - It is guaranteed that for any function call to
erase
, the stringword
will exist in the trie.
Solutions
Solution 1: Implement Trie with Array
Each node in the Trie includes three parts:
- An array of pointers
children
pointing to child nodes. For this problem, the array length is 26, which is the number of lowercase English letters.children[0]
corresponds to the lowercase letter a, ...,children[25]
corresponds to the lowercase letter z. - An int variable
v
, representing the number of strings ending with this node. - An int variable
pv
, representing the number of strings with this node as the prefix node.
1. Insert String
We start from the root of the Trie and insert the string. For the child node corresponding to the current character, there are two cases:
- The child node exists. Move to the child node along the pointer and continue to process the next character.
- The child node does not exist. Create a new child node, record it in the corresponding position of the
children
array, then move to the child node along the pointer, and increase thepv
value of the child node by 1. Continue to search for the next character.
Repeat the above steps until the last character of the string is processed, then increase the v
value of the current node by 1.
The time complexity is $O(n)$, where $n$ is the length of the string.
2. Search Prefix
We start from the root of the Trie and search for the prefix. For the child node corresponding to the current character, there are two cases:
- The child node exists. Move to the child node along the pointer and continue to search for the next character.
- The child node does not exist. This means that the Trie does not contain this prefix, return a null pointer.
Repeat the above steps until a null pointer is returned or the last character of the prefix is searched.
The time complexity is $O(n)$, where $n$ is the length of the string.
3. Remove String
We start from the root node of the Trie, and sequentially reduce the pv
value of the corresponding child node by 1, until the last character of the string is searched. Then reduce the v
value of the current node by 1.
The time complexity is $O(n)$, where $n$ is the length of the string.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 |
|