“This article has participated in the call for good writing activities, click to view: the back end, the big front end double track submission, 20,000 yuan prize pool waiting for you to challenge!”

Often have readers ask xiaobian, said that with ShowMeBug pen interview programming questions when the code automatic completion function experience is particularly good, want to know how to achieve. Ask more people, xiaobian will arrange an article to explain the principle of automatic completion.

The most common autocomplete scenario in our daily life is the search box of a search engine, as shown below:

Surely the simplest and most crude way is to prefix the search terms entered by the user with the strings in the list, and if the prefix matches, it is displayed in the search results. This is acceptable when the set of strings to search for is small, but less efficient when the set of objects to search for is large.

const texts = ["show"."me"."bug"."money"];

const createFilter = (queryString) = > {
  return (text) = > {
    return (
      text.toLowerCase().indexOf(queryString.toLowerCase()) ===
          0
    );
  };
};

texts.find(createFilter('sh')) // return show
Copy the code

If not, consider dictionary trees. To quote wikipedia’s definition of a dictionary tree:

A dictionary tree is an ordered tree used to hold associative arrays where the keys are usually strings. Unlike binary lookup trees, keys are not stored directly in a node, but are determined by the node’s position in the tree. All descendants of a node have the same prefix, which is the string corresponding to the node, and the root node corresponds to the empty string.

Because it is a tree, its query efficiency is very high. If the length of the string to be queried is K, the search time complexity is O(k).

However, dictionary trees are space-intensive, and although you can further save space with a three-way dictionary tree, they are sufficient for this purpose.

First, we need to build a dictionary tree, so how do we build it?

Unlike binary trees, dictionary trees have multiple forks. A common implementation is to build A dictionary tree by mapping multiple levels of arrays, assuming that the input string has only 26 lower-case letters. The first-level node is A 26-element array A with the subscript 0 for A, and so on. If the character s is followed by the character H, the value of s in array A stores another 26-element array B, and C in the subscript of character S in array B, and so on.

class TrieNode {
    data;
    children = Array(26);
    isEndingChar = false;
    constructor(data) {
        this.data = data; }}class Trie {
    root = new TrieNode('/');

    insert(text) {
        let p = this.root;
        for (let i = 0; i < text.length; i++) {
            const idx = text[i].charCodeAt() - 'a'.charCodeAt();

            if(! p.children[idx]) {const newNode = new TrieNode(text[i]);
                p.children[idx] = newNode;
            }
            p = p.children[idx];
        }
        p.isEndingChar = true;
    }

    find(pattern) {
        let p = this.root;
        for (let i = 0; i < pattern.length; i++) {const idx = pattern[i].charCodeAt() - 'a'.charCodeAt();
            if(! p.children[idx]) {return false;
            }
            p = p.children[idx];
        }

        returnp.isEndingChar; }}function main() {
    const trie = new Trie();
    trie.insert("show");
    trie.insert("me");
    trie.insert("bug");
    console.log(trie.find('sh')) // return false
    console.log(trie.find('show')) // return true
}

main()
Copy the code

Now that you understand how autocomplete works, you may want to consider a dictionary tree for your next pen interview with ShowMeBug