This is the 30th day of my participation in the wenwen Challenge

This series is nothing fancy, just pure Leetcode problem breakdown analysis, not to use a sexy line or a niche solution, but with clear code and simple enough thinking to help you clarify the problem. Let you in the interview no longer afraid of algorithm written test.

Implement Trie (prefix tree/dictionary tree) (implement-trie-prefix-tree)

The label

  • Trie prefix tree/dictionary tree
  • medium

The title

Leetcode portal

Let’s just open leetCode.

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()Initialize 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.

Example 1

Input ["Trie"."insert"."search"."search"."startsWith"."insert"."search"[[]], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"[]] outputnull.null.true.false.true.null.true[explain 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
Copy the code

The basic idea

We were introduced to a data structure, Trie

Tire trees are also called dictionary trees. It is a tree structure that deals specifically with string matching data structures to solve the problem of quickly finding a string in a collection of strings. Search engine prompts, for example

The blue box is a hint, so there’s a lot of words, a lot of words, how do you quickly match the input, and that’s how you trade space for time. This graph is an example, not to say that Google is structured this way.

Here’s an example to illustrate

Build trie tree with how, Hi, her, Hello, so, see as data set

The insertion process is as follows

The path from root to leaf is a word. The red dot is the leaf, the end of a string.

And it ends up like this

Of course, matching strings by prefix is much more efficient than traversing, and the core is space for time.

The storage method is to store Pointers to child nodes in an array of subscripts and characters mapped one by one.

Writing implement

The implementation is not too difficult, and the code and comments should be clear.

var Trie = function() {
  this.children = {}
};

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


Trie.prototype.searchPrefix = function(prefix) {
  let node = this.children
  for (ch of prefix) {
    if(! node[ch]) {return false
    }
    node = node[ch]
  }
  return node
};

/**
 * Returns if the word is in the trie. 
 * @param {string} word
 * @return {boolean}* /
Trie.prototype.search = function(word) {
  let node = this.searchPrefix(word)
  returnnode ! = =undefined&& node.isEnd ! = =undefined
};

Trie.prototype.startsWith = function(prefix) {
  return Boolean(this.searchPrefix(prefix))
};

/ / test
let trie = new Trie();
trie.insert("apple");
// Look at the trie structure after insert to make it clear
// console.log(trie)
/ / {
// "children":{
// "a":{
// "p":{
// "p":{
// "l":{
// "e":{
// "isEnd":true
/ /}
/ /}
/ /}
/ /}
/ /}
/ /}
// }
console.log(trie.search("apple")) 
// Return true if isEnd is true
console.log(trie.search("app"))
// Return false, since the end is not reached, we can only say that the prefix is matched, not the word
console.log(trie.startsWith("app"))
// Find the prefix this time

trie.insert("app");
// console.log(trie)
/ / {
// "children":{
// "a":{
// "p":{
// "p":{
// "l":{
// "e":{
// "isEnd":true
/ /}
/ /},
// "isEnd":true // There is also an app word end
/ /}
/ /}
/ /}
/ /}
// }

console.log(trie.search("app"))
// true
Copy the code

In addition, we recommend this series of articles, very simple, on the front of the advanced students are very effective, wall crack recommended!! Core concepts and algorithm disassembly series

If you want to brush the questions with me, you can add me on wechat. Click here to make a friend Or search my wechat account, infinity_9368. You can chat with me and add my secret code “Tianwang Gaidihu”. Verify the message please send me Presious tower shock the rever Monster, I see it through, after adding I will do my best to help you, but pay attention to the way of asking questions, it is suggested to read this article: the wisdom of asking questions

reference