ShowMeBug 自动补全功能原理大揭秘-一一网

「本文已参与好文召集令活动，点击查看：后端、大前端双赛道投稿，2万元奖池等你挑战！」

经常有读者问小编，说用 ShowMeBug 做笔面试编程题时代码自动补全功能体验特别好，想知道是怎么实现的。问的人多了，小编就安排了一篇文章来说明自动补全的原理。

我们日常生活中最常见的自动补全场景是搜索引擎的搜索框，比如下图：

最简单粗暴的方式肯定是将用户输入的搜索词依次与列表中的字符串进行前缀匹配，如果前缀匹配，就在搜索结果中显示。当要搜索的字符串集合较小时，这么做可以接受，但如果搜索对象集较大，就不那么高效了。

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

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

texts.find(createFilter('sh')) // return show
复制代码

如果不用这种方式，那就要考虑字典树了。引用维基百科中关于字典树的定义：

字典树是一种有序树，用于保存关联数组，其中的键通常是字符串。与二叉查找树不同，键不是直接保存在节点中，而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀，也就是这个节点对应的字符串，而根节点对应空字符串。

因为是树，其查询效率非常高，如果要查询的字符串长度是k，则查找的时间复杂度为O(k)。

不过字典树比较耗费空间，虽然可以通过三向字典树来进一步节省空间，但对于目前这个需求来说，字典树就够了。

首先，我们要构建一棵字典树，那该怎么构建呢？

和二叉树不同，字典树有多个分叉，常见的实现是通过多层数组映射来构建，假设输入的字符串只有 26 个小写英文字母，第一层节点是一个包含 26 个元素的数组A，数组A下标 0 表示a，依次类推；如果输入的字符s后面还有字符h，则此时数组A中s的值会保存另一个包含 26 个元素的数组B，并在数组B中表示字符s的下标中再存储一个数组C，依次类推。

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];
        }

        return p.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()
复制代码