求原理和实现: 部分字符的建议补全

Question

1. Content assist provides you with a list of suggested completions for partially entered strings.
   内容协助为您提供部分输入的字符串的建议完成列表。

2. 描述大概如上，我不知道怎么用一个更精确的词来形容。

3. sublime中有这个功能，你输入“不完整的字符”，它会给你返回，包含这些字母的所有结果。譬如：输入 ds 可以得到 desk ，尽管中间间隔了一个 字母 e。

4. 我就想知道这是怎么实现的，原理是什么？

5. 而且，这个功能，有名字吗（我其实不知道这个功能应该叫啥名字，所以也妨碍了在网上搜寻答案）？

Answer 1

这个功能，应该叫“搜索智能提示”实现办法有很多种，但是我只知道最简单最容易理解的一种，复杂的对查询算法做了优化，效率更高，可能涉及到动态规划问题。如果是最简单的方法，就是把字符串拆开，然后向每两个字中间放入一个.*，再将其生成正则，用这个正则去匹配列表JS伪代码：var list = [ ... ];var text = 'ds';var result = [];if(text != '') {    var pattern = new RegExp(text.split('').join('.*'));    result = list.filter(function(item) {        return pattern.test(item);    });}演示效果：