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

Question

Content assist provides you with a list of suggested completions for partially entered strings.内容协助为您提供部分输入的字符串的建议完成列表。描述大概如上，我不知道怎么用一个更精确的词来形容。sublime中有这个功能，你输入“不完整的字符”，它会给你返回，包含这些字母的所有结果。譬如：输入 ds 可以得到 desk ，尽管中间间隔了一个 字母 e。我就想知道这是怎么实现的，原理是什么？而且，这个功能，有名字吗（我其实不知道这个功能应该叫啥名字，所以也妨碍了在网上搜寻答案）？

Answer 1

1. 这个功能，应该叫“搜索智能提示”

2. 实现办法有很多种，但是我只知道最简单最容易理解的一种，复杂的对查询算法做了优化，效率更高，可能涉及到动态规划问题。

3. 如果是最简单的方法，就是把字符串拆开，然后向每两个字中间放入一个.*，再将其生成正则，用这个正则去匹配列表

4. 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);

    });

}

演示效果：