GeezerVison is showing github.com — Update README. · src93/javascript-algorithms@15e798c
File treeExpand file treeCollapse file tree Open diff view settings sets/longest-common-subsequnce string/longest-common-subsequnce/__test__
Expand file treeCollapse file tree Open diff view settings Collapse file Copy file name to clipboardExpand all lines: README.md +3-3Lines changed: 3 additions & 3 deletions - Display the source diff
- Display the rich diff
| Original file line number | Diff line number | Diff line change |
|---|
| 38 | 38 | * [Power Set](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sets/power-set) - all subsets of the set | 39 | 39 | * [Permutations](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sets/permutations) (with and without repetitions) | 40 | 40 | * [Combinations](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sets/combinations) (with and without repetitions) | 41 | | - * [Fisher–Yates Shuffle](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sets/fisher-yates) - random permutation of a finite sequence | | 41 | + * [Fisher–Yates Shuffle](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sets/fisher-yates) - random permutation of a finite sequence | | 42 | + * [Longest Common Subsequence](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sets/longest-common-subsequnce) (LCS) | 42 | 43 | * **String** | 43 | 44 | * [Levenshtein Distance](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/string/levenshtein-distance) - minimum edit distance between two sequences | 44 | 45 | * [Hamming Distance](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/string/hamming-distance) - number of positions at which the symbols are different | 45 | 46 | * [Knuth–Morris–Pratt Algorithm](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/string/knuth-morris-pratt) - substring search | 46 | 47 | * [Rabin Karp Algorithm](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/string/rabin-karp) - substring search | 47 | | - * [Longest Common Subsequence](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/string/longest-common-subsequnce) (LCS) | 48 | 48 | * [Longest Common Substring](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/string/longest-common-substring) | 49 | 49 | * **Search** | 50 | 50 | * [Binary Search](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/search/binary-search) | | 90 | 90 | * **Dynamic Programming** | 91 | 91 | * [Fibonacci Number](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/math/fibonacci) | 92 | 92 | * [Levenshtein Distance](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/string/levenshtein-distance) - minimum edit distance between two sequences | 93 | | - * [Longest Common Subsequence](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/string/longest-common-subsequnce) (LCS) | | 93 | + * [Longest Common Subsequence](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sets/longest-common-subsequnce) (LCS) | 94 | 94 | * [Longest Common Substring](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/string/longest-common-substring) | 95 | 95 | * Increasing subsequence | 96 | 96 | * Longest Increasing subsequence | |
Collapse file Copy file name to clipboard - Display the source diff
- Display the rich diff
File renamed without changes. Collapse file Copy file name to clipboard +31Lines changed: 31 additions & 0 deletions | Original file line number | Diff line number | Diff line change |
|---|
| | 1 | +import longestCommonSubsequnce from '../longestCommonSubsequnce'; | | 2 | + | | 3 | +describe('longestCommonSubsequnce', () => { | | 4 | + it('should find longest common subsequence for two strings', () => { | | 5 | + expect(longestCommonSubsequnce([''], [''])).toEqual(['']); | | 6 | + | | 7 | + expect(longestCommonSubsequnce([''], ['A', 'B', 'C'])).toEqual(['']); | | 8 | + | | 9 | + expect(longestCommonSubsequnce(['A', 'B', 'C'], [''])).toEqual(['']); | | 10 | + | | 11 | + expect(longestCommonSubsequnce( | | 12 | + ['A', 'B', 'C'], | | 13 | + ['D', 'E', 'F', 'G'], | | 14 | + )).toEqual(['']); | | 15 | + | | 16 | + expect(longestCommonSubsequnce( | | 17 | + ['A', 'B', 'C', 'D', 'G', 'H'], | | 18 | + ['A', 'E', 'D', 'F', 'H', 'R'], | | 19 | + )).toEqual(['A', 'D', 'H']); | | 20 | + | | 21 | + expect(longestCommonSubsequnce( | | 22 | + ['A', 'G', 'G', 'T', 'A', 'B'], | | 23 | + ['G', 'X', 'T', 'X', 'A', 'Y', 'B'], | | 24 | + )).toEqual(['G', 'T', 'A', 'B']); | | 25 | + | | 26 | + expect(longestCommonSubsequnce( | | 27 | + ['A', 'B', 'C', 'D', 'A', 'F'], | | 28 | + ['A', 'C', 'B', 'C', 'F'], | | 29 | + )).toEqual(['A', 'B', 'C', 'F']); | | 30 | + }); | | 31 | +}); |
Collapse file Copy file name to clipboard +18-18Lines changed: 18 additions & 18 deletions | Original file line number | Diff line number | Diff line change |
|---|
| 1 | 1 | /** | 2 | | - * @param {string} s1 | 3 | | - * @param {string} s2 | 4 | | - * @return {string} | | 2 | + * @param {string[]} set1 | | 3 | + * @param {string[]} set2 | | 4 | + * @return {string[]} | 5 | 5 | */ | 6 | | -export default function longestCommonSubsequnce(s1, s2) { | | 6 | +export default function longestCommonSubsequnce(set1, set2) { | 7 | 7 | // Init LCS matrix. | 8 | | - const lcsMatrix = Array(s2.length + 1).fill(null).map(() => Array(s1.length + 1).fill(null)); | | 8 | + const lcsMatrix = Array(set2.length + 1).fill(null).map(() => Array(set1.length + 1).fill(null)); | 9 | 9 |
| 10 | 10 | // Fill first row with zeros. | 11 | | - for (let columnIndex = 0; columnIndex <= s1.length; columnIndex += 1) { | | 11 | + for (let columnIndex = 0; columnIndex <= set1.length; columnIndex += 1) { | 12 | 12 | lcsMatrix[0][columnIndex] = 0; | 13 | 13 | } | 14 | 14 |
| 15 | 15 | // Fill first column with zeros. | 16 | | - for (let rowIndex = 0; rowIndex <= s2.length; rowIndex += 1) { | | 16 | + for (let rowIndex = 0; rowIndex <= set2.length; rowIndex += 1) { | 17 | 17 | lcsMatrix[rowIndex][0] = 0; | 18 | 18 | } | 19 | 19 |
| 20 | 20 | // Fill rest of the column that correspond to each of two strings. | 21 | | - for (let rowIndex = 1; rowIndex <= s2.length; rowIndex += 1) { | 22 | | - for (let columnIndex = 1; columnIndex <= s1.length; columnIndex += 1) { | 23 | | - if (s1[columnIndex - 1] === s2[rowIndex - 1]) { | | 21 | + for (let rowIndex = 1; rowIndex <= set2.length; rowIndex += 1) { | | 22 | + for (let columnIndex = 1; columnIndex <= set1.length; columnIndex += 1) { | | 23 | + if (set1[columnIndex - 1] === set2[rowIndex - 1]) { | 24 | 24 | lcsMatrix[rowIndex][columnIndex] = lcsMatrix[rowIndex - 1][columnIndex - 1] + 1; | 25 | 25 | } else { | 26 | 26 | lcsMatrix[rowIndex][columnIndex] = Math.max( | @@ -32,19 +32,19 @@ export default function longestCommonSubsequnce(s1, s2) { | 32 | 32 | } | 33 | 33 |
| 34 | 34 | // Calculate LCS based on LCS matrix. | 35 | | - if (!lcsMatrix[s2.length][s1.length]) { | | 35 | + if (!lcsMatrix[set2.length][set1.length]) { | 36 | 36 | // If the length of largest common string is zero then return empty string. | 37 | | - return ''; | | 37 | + return ['']; | 38 | 38 | } | 39 | 39 |
| 40 | | - let lcs = ''; | 41 | | - let columnIndex = s1.length; | 42 | | - let rowIndex = s2.length; | | 40 | + const longestSequence = []; | | 41 | + let columnIndex = set1.length; | | 42 | + let rowIndex = set2.length; | 43 | 43 |
| 44 | 44 | while (columnIndex > 0 || rowIndex > 0) { | 45 | | - if (s1[columnIndex - 1] === s2[rowIndex - 1]) { | | 45 | + if (set1[columnIndex - 1] === set2[rowIndex - 1]) { | 46 | 46 | // Move by diagonal left-top. | 47 | | - lcs = s1[columnIndex - 1] + lcs; | | 47 | + longestSequence.unshift(set1[columnIndex - 1]); | 48 | 48 | columnIndex -= 1; | 49 | 49 | rowIndex -= 1; | 50 | 50 | } else if (lcsMatrix[rowIndex][columnIndex] === lcsMatrix[rowIndex][columnIndex - 1]) { | @@ -56,5 +56,5 @@ export default function longestCommonSubsequnce(s1, s2) { | 56 | 56 | } | 57 | 57 | } | 58 | 58 |
| 59 | | - return lcs; | | 59 | + return longestSequence; | 60 | 60 | } |
Collapse file Copy file name to clipboardExpand all lines: src/algorithms/string/longest-common-subsequnce/__test__/longestCommonSubsequnce.test.js -13Lines changed: 0 additions & 13 deletions
|