How do you implement the " Command+P" function?

As a programer, you may probably use ⌘+P a lot to search your file, conveniently, you don't have to enter the full path,it can also get the result you want, see the example below:

The blue highlight text is your input, it's not a complete path but the editor still get you the correct file, so, here is the question: how do we implement the ⌘+P function?

LCS

The key is Longest Common Subsequence,for example:

Input: str1 = "abcdef", str2 = "bcfg"
Output: "bcf"
Explanation: "a", "ac", "bcd", "bcf"...are the subsequence of "abcdef", "bcfg" also have some subsequences, the longest common subsequence is "bcf"

Solution:
Continuing with the example above, S(a, b) means the LCS of a and b and we need to get S("abcdef", "bcfg").

Step1:
The last char of strings is not equal, so
S("abcdef", "bcfg") = Max(S("abcdef", "bcf"), S("abcde", "bcfg"))

Step2: let S("abcdef", "bcf") as our target
The last char of strings is equal, so
S("abcdef", "bcf") = S("abcde", "bc") + 1

Repeat step1 and step2, we can get the answer, here is the code:

function getLCS(str1, str2) { 
    let record = Array.from({ length: str1.length }, () => { 
        return Array.from({ length: str2.length });
    });

    function find(index1, index2) { 
        if (index1 < 0 || index2 < 0) return { len: 0, match: [] };
        if (record[index1][index2] !== undefined) return record[index1][index2];

        let ans = record[index1][index2] = {
            len: 0, 
            match: [],
        }
        if (str1[index1] === str2[index2]) {
            ans.len = 1;
            ans.match.push([index1, index2]);

            let chAns = find(index1 - 1, index2 - 1);
            ans.len += chAns.len;
            ans.match.push(...chAns.match);
        } else { 
            let chAns1 = find(index1 - 1, index2);
            let chAns2 = find(index1, index2 - 1);
            ans = record[index1][index2] = chAns1.len > chAns2.len ? chAns1 : chAns2;
        }

        return ans;
    }

    let ans = find(str1.length - 1, str2.length - 1);
    ans.match.reverse();
    let len = ans.len;
    let str = "";
    for (let i = 0, l = ans.match.length; i < l; i++) { 
        str += str1[ans.match[i][0]]
    };

    return {
        length: len,
        str: str,
        detail: ans
    }
}

⌘+P

If we get the whole path of all files, and the target is your input, for example:

let filePaths = [
"vue2/vue-2.6/src/core/observer/array.js",
"vue2/vue-2.6/src/core/observer/dep.js",
"vue2/vue-2.6/src/core/observer/index.js",
// ...
];

let target = "vue/src/ob/arr";

each item of filePaths get the LCS with target,we may get results:

let res = filePaths.map(path => getLCS(target, path).str);
console.log(res); // ['vue/src/ob/arr', 'vue/src/o/rr', 'vue/src/o/rr']

but that's not enough, the matched char should be highlighted, so let's add the highlight code:

function highlightRes(target, matchs) {
    if (!matchs.length) return target;

    let ans = "";
    let lastIndex = -1;
    for (let i = 0; i < matchs.length; i++) {
        let charIndex = matchs[i][0];
        let highlightChar = `<span style="color: red;">${target[charIndex]}</span>`;
        ans += (target.slice(lastIndex + 1, charIndex) + highlightChar);
        lastIndex = charIndex;
    }
    if (lastIndex !== target.length - 1) {
        ans += target.slice(lastIndex + 1, target.length);
    }

    return ans;
}

Demo

let filePaths = [
    "vue2/vue-2.6/src/core/observer/array.js",
    "vue2/vue-2.6/src/core/observer/dep.js",
    "vue2/vue-2.6/src/core/observer/index.js",
    // ...
];

let target = "vue/src/ob/arr";

let ipt = document.createElement("input");
let container = document.createElement("div");
document.body.innerHTML = ``;
document.body.appendChild(ipt);
document.body.appendChild(container)
ipt.addEventListener("input", (e) => {
    let content = e.target.value;
    if (!content) {
        container.innerHTML = ``;
        return;
    };

    let res = filePaths.map(path => {
        return highlightRes(path, getLCS(path, content).detail.match)
    });
    container.innerHTML = `
    <div>
        <h3>Search value: ${content}</h3>
        <h3>FilePaths: </h3>
        <div>
            ${filePaths.map(item => {
                return `<div>${item}</div>`
            }).join("")}
        </div>

        <h3>Search result: </h3>
        <div>
            ${res.map(item => {
                return `<div>${item}</div>`
            }).join("")}
        </div>
    </div`
});

The end

There are still some places that can be optimized in this program,for example:

How should we sort the results by continuity of characters? Continuous result is better than decentralized
How can we make the search faster?

Hope you can resolve these issues or share some of your own thoughts😊.

Blog

How do you implement the " Command+P" function?

dk_bfm

LCS

⌘+P

Demo

The end

Join Our Newsletter. No Spam, Only the good stuff.

Related