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😊.
Top comments (0)