Technology Sharing

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

原题链接🔗：Implementing Trie (prefix tree)
Difficulty: Medium ⭐️⭐️

topic

Trie (pronounced like "try") or Prefix Tree It is a tree data structure used to efficiently store and retrieve keys from a string data set. This data structure has many applications, such as auto-completion and spell checking.

Please implement the Trie class:

• Trie() Initialize a prefix tree object.
• void insert(String word) Insert a string into the prefix treeword 。
• boolean search(String word) If the stringword In the prefix tree, return true(i.e., it has been inserted before being retrieved); otherwise, returns false 。
• boolean startsWith(String prefix) If the string has been inserted before wordOne of the prefixes is prefix ,return true ; Otherwise, returnfalse。

Example:

enter
[“Trie”, “insert”, “search”, “search”, “startsWith”, “insert”, “search”]
[[], [“apple”], [“apple”], [“app”], [“app”], [“app”], [“app”]]
Output
[null, null, true, false, true, null, true]

explain
Trie trie = new Trie();
trie.insert(“apple”);
trie.search("apple"); // returns True
trie.search("app"); // returns False
trie.startsWith("app"); // returns True
trie.insert(“app”);
trie.search("app"); // returns True

hint:

• 1 <= word.length, prefix.length <= 2000
• word and prefix consist only of lowercase English letters
• The total number of insert, search and startsWith calls does not exceed 3 * 10⁴ Second-rate

Prefix Tree

A prefix tree, also known as a Trie tree (pronounced "try"), is a data structure used to store a collection of strings, which allows fast retrieval and insertion of strings, as well as querying string prefixes. Each node of the prefix tree represents a prefix of a string, and the children of each node represent all possible extensions of the prefix by adding one character.

• Characteristics of prefix tree：
  • Space efficiency: For a set of strings with a large number of common prefixes, a prefix tree can save storage space.
  • Time efficiency: The time complexity of insertion and search operations is usually O(m), where m is the length of the string.
  • Dynamic Collection: The prefix tree can dynamically insert and delete strings and is suitable for scenarios that require frequent updates.
• Basic operations of prefix tree：
  • insert: Insert a string into the tree, starting from the root node and going down character by character. If the child node corresponding to the character does not exist, a new node is created.
  • search: Search whether a string exists in the tree, starting from the root node and going down character by character. If the child node of a character does not exist, the search fails.
  • Prefix Search: Checks whether there are any strings prefixed with a certain string, similar to the search operation, but there is no need to check the end flag of the last node.
  • delete: To delete a string from the tree, you need to recursively delete nodes while ensuring that common prefix nodes of other strings are not deleted.
• Application scenarios of prefix trees：
  • Autocomplete: In search engines or text editors, quickly provide completion suggestions based on the prefix entered by the user.
  • Spell Check: Checks whether the word entered by the user is spelled correctly and provides correct spelling suggestions.
  • IP Routing: In the network, the longest prefix match is used to determine the routing path of the data packet.
  • Gene sequence analysis: In bioinformatics, used for rapid matching and retrieval of gene sequences.

answer

1. Problem Solving：

Trie (prefix tree) is a tree data structure used to quickly retrieve keys in a string data set. It is a special tree in which each node represents a character and the path from the root to a node represents a string. Trie trees are often used to implement functions such as auto-completion and spell checking.

The following are the basic steps and problem-solving ideas for implementing the Trie tree:

1. Defining Trie Nodes：

   • Each Trie node typically contains a set of characters or a Boolean value to indicate the end of a word, and pointers to child nodes.

2. Initializing the Trie：

   • Create a root node that contains no characters but serves as the starting point for all words.

3. Insert Operation：

   • Starting at the root node, for each character in the string to be inserted:
     • If the child node corresponding to the character does not exist, a new child node is created.
     • Move the current node to the corresponding child node.

4. Search Operation：

   • Starting at the root node, for each character in the string you are searching for:
     • If the child node corresponding to the character exists, continue searching.
     • If it does not exist, the search fails.

5. Prefix Search：

   • Similar to the search operation, but only cares whether the prefix of the string exists.

6. Delete Operation(Optional):

   • Implement word deletion functionality as needed, which usually involves deleting nodes and requires handling node reference counts.

7. Auto-completion(Optional):

   • Given a prefix, return all strings that begin with that prefix.

2. c++ demo：

#include <iostream>
#include <string>
#include <unordered_map>

using namespace std;

class Trie {
private:
    vector<Trie*> children;
    bool isEnd;

    Trie* searchPrefix(string prefix) {
        Trie* node = this;
        for (char ch : prefix) {
            ch -= 'a';
            if (node->children[ch] == nullptr) {
                return nullptr;
            }
            node = node->children[ch];
        }
        return node;
    }

public:
    Trie() : children(26), isEnd(false) {}

    void insert(string word) {
        Trie* node = this;
        for (char ch : word) {
            ch -= 'a';
            if (node->children[ch] == nullptr) {
                node->children[ch] = new Trie();
            }
            node = node->children[ch];
        }
        node->isEnd = true;
    }

    bool search(string word) {
        Trie* node = this->searchPrefix(word);
        return node != nullptr && node->isEnd;
    }

    bool startsWith(string prefix) {
        return this->searchPrefix(prefix) != nullptr;
    }
};


int main() {
    Trie trie;
    trie.insert("apple");
    std::cout << trie.search("apple") << std::endl;   // 返回 1
    std::cout << trie.search("app") << std::endl;     // 返回 0
    std::cout << trie.startsWith("app") << std::endl; // 返回 1

    return 0;
}
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

• Output:

1
0
1

3. Code repository address：Trie