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: ![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/aia9ujteio3pmpnupokw.png) 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: ```javascript 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: ```javascript 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: ```javascript 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: ```javascript 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 = `${target[charIndex]}`; ans += (target.slice(lastIndex + 1, charIndex) + highlightChar); lastIndex = charIndex; } if (lastIndex !== target.length - 1) { ans += target.slice(lastIndex + 1, target.length); } return ans; } ``` ### Demo ![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/2g513376ajifbkh8hvwp.png) ```javascript 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 = `

Search value: ${content}

FilePaths:

${filePaths.map(item => { return `

${item}

` }).join("")}

Search result:

${res.map(item => { return `

${item}

` }).join("")}

dk_bfm

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

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