How to implement trie in the algorithm

This article mainly introduces "how to achieve trie in the algorithm". In the daily operation, I believe many people have doubts about how to achieve trie in the algorithm. The editor consulted all kinds of materials and sorted out simple and easy-to-use operation methods. I hope it will be helpful for you to answer the doubts about "how to achieve trie in the algorithm". Next, please follow the editor to study!

Algorithm:

The prefix tree is mainly used to search the algorithm, the idea and implementation are not complex, it is a typical topic, the algorithm is as follows:

1. Up to n links to child nodes, where each link corresponds to a letter in the alphabet data set. This article assumes that n is 26, the number of lowercase Latin letters. two。 Boolean field to specify whether the node corresponds to the end of the key or just the key prefix

Code implementation:

Type Trie struct {IsEnd bool Link [26] * Trie}

/ * Initialize your data structure here. * / func Constructor () Trie {root: = Trie {} return root}

/ * Inserts a word into the trie. * / func (this * Trie) Insert (word string) {var node * Trie = this for _, w: = range [] byte (word) {if node.Link [w-byte ('a')] = = nil {n: = Trie {} node.Link [w-byte ('a')] = & n} node = node.Link [w-byte ('a')]} node.IsEnd = true return}

/ * Returns if the word is in the trie. * / func (this * Trie) Search (word string) bool {var node * Trie = this for _, w: = range [] byte (word) {if node.Link [w-byte ('a')] = = nil {node = nil break} node = node.Link [w-byte ('a')]} return node! = nil & node.IsEnd}

/ * Returns if there is any word in the trie that starts with the given prefix. * / func (this * Trie) StartsWith (prefix string) bool {var node * Trie = this for _, w: = range [] byte (prefix) {if node.Link [w-byte ('a')] = = nil {node = nil break} node = node.Link [w-byte ('a')]} return node! = nil}

/ * Your Trie object will be instantiated and called as such: * obj: = Constructor (); * obj.Insert (word); * param_2: = obj.Search (word); * param_3: = obj.StartsWith (prefix); * /

Execution result:

At this point, the study of "how to implement trie in the algorithm" is over. I hope to be able to solve your doubts. The collocation of theory and practice can better help you learn, go and try it! If you want to continue to learn more related knowledge, please continue to follow the website, the editor will continue to work hard to bring you more practical articles!