javascript - Principle and implementation: Suggested completion of some characters

Question

1. Content assist provides you with a list of suggested completions for partially entered strings.
   Content assist provides you with a list of suggested completions for partially entered strings.

2. The description is roughly as above, I don’t know how to use a more precise word to describe it.

There is this function in

3. sublime. You enter "incomplete characters" and it will return to you all results containing these letters. For example: Enter ds to get desk , even though there is a letter e in the middle.

4. I just want to know how this is achieved and what is the principle?

5. Also, does this function have a name (I actually don’t know what this function should be called, so it also hinders searching for answers on the Internet)?

Answer 1

@boxsnake gave an example of searching an array. The returned results should be sorted. "avsdsss" has the highest priority, as it contains consecutive "ds". "Everybody" should also hit, it contains "d".

The time complexity of searching the array is too high. When there are many keywords, the speed is basically unacceptable.

The efficient and feasible method is to use string search tree.
Trie tree (dictionary tree) for massive data processing

Answer 2

1. This function should be called “Search Smart Tips”

2. There are many ways to implement it, but I only know the simplest and easiest to understand one. The complex query algorithm is optimized, which is more efficient and may involve dynamic programming problems.

3. If it is the simplest method, it is to split the string, and then put a .* between every two characters, then generate a regular expression, and use this regular expression to match the list

4. JS pseudo code:

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

Demonstration effect: