“This is the 16th day of my participation in the First Challenge 2022. For details: First Challenge 2022.”

Introduction to the

Prefix tree, also known as word lookup tree, Trie tree, is a tree structure, is a variant of the hash tree. It is typically used to count, sort and save large numbers of strings (but not limited to strings), so it is often used for text word frequency statistics by search engine systems. Its advantages are that it reduces query time by using the common prefix of strings, minimizes unnecessary string comparisons, and improves query efficiency over hash trees. It has three basic properties: the root node contains no characters, and every node except the root node contains only one character; From the root node to a node, the characters on the path are connected to the string corresponding to the node. All children of each node contain different characters.

example

The title

A Trie (pronounced like “try”) or prefix tree is a tree data structure for efficiently storing and retrieving keys in a string data set. This data structure has a number of applications, such as auto-completion and spell checking.

Please implement Trie class:

Trie() initializes the prefix tree object. Void insert(String word) Inserts the String word into the prefix tree. Boolean search(String word) Returns true if the String word is in the prefix tree (that is, inserted before retrieval); Otherwise, return false. Boolean startsWith(String prefix) Returns true if one of the prefixes of the previously inserted String word is prefix; Otherwise, return false.

Source: LeetCode link: leetcode-cn.com/problems/im… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

The sample

The input

[“Trie”, “insert”, “search”, “search”, “startsWith”, “insert”, “search”] [[], [“apple”], [“apple”], [“app”], [“app”], [“app”], [“app”]]

The output

[null, null, true, false, true, null, true]

explain

Trie trie = new Trie();

trie.insert(“apple”);

trie.search(“apple”); / / return True

trie.search(“app”); / / returns False

trie.startsWith(“app”); / / return True

trie.insert(“app”);

trie.search(“app”); / / return True

Code implementation

Train of thought

A prefix tree is essentially a tree structure. Each node stores a letter and connects the next letter, so that multiple letters can be connected to form a complete word, as shown in the following figure:

The figure above can represent two words: APP and APPLE. When searching for a word, we should start from the root node until the isEnd tag is matched, which means that all letters from the root node to the node can form a complete word. The specific implementation code is as follows:

code

/** * Initialize your data structure here. */
var Trie = function() {
    this.tree = {};
};

/**
 * Inserts a word into the trie. 
 * @param {string} word
 * @return {void}* /
Trie.prototype.insert = function(word) {
    let tree = this.tree;
    for(const w of word){
        if(tree[w] == undefined){
            tree[w] = {};
        }
        tree = tree[w];
    }
    tree.isEnd = true;
};

/**
 * Returns if the word is in the trie. 
 * @param {string} word
 * @return {boolean}* /
Trie.prototype.search = function(word) {
    let tree = this.tree;
    for(const w of word){
        if(tree[w] == undefined) {return false;
        }
        tree = tree[w];
    }
    return tree.isEnd == true;
};

/**
 * Returns if there is any word in the trie that starts with the given prefix. 
 * @param {string} prefix
 * @return {boolean}* /
Trie.prototype.startsWith = function(prefix) {
    let tree = this.tree;
    for(const w of prefix){
        if(tree[w] == undefined) {return false;
        }
        tree = tree[w];
    }
    return true;
};

/** * Your Trie object will be instantiated and called as such: * var obj = new Trie() * obj.insert(word) * var param_2 = obj.search(word) * var param_3 = obj.startsWith(prefix) */
Copy the code

application

Prefix trees can be used in many places, such as:

Quick retrieval of strings

Given a list of N words and an article written in all lowercase English, please write down all the new words that are not in the list in the order that they appear first. In this problem, we can use array enumeration, hash, dictionary tree, the first familiar words to build a tree, and then read into the article for comparison, this method is relatively high efficiency.

“String” sort

Given N distinct one-word names, let you sort them lexicographically from smallest to largest in a dictionary tree. Create a dictionary tree as an array. All the sons of each node of the tree are obviously sorted by their letter size. Just do a preemptive walk through the tree.

Longest public prefix

The dictionary tree is established for all strings, and the length of the longest common prefix of two strings is the number of common ancestors of the node where they are located. Then, the problem is transformed into the problem of common ancestors at that time.