5 kyu
Longest Common Subsequence
2,040 of 6,943xDranik
Description:
Write a function called LCS
that accepts two sequences and returns the longest subsequence common to the passed in sequences.
Subsequence
A subsequence is different from a substring. The terms of a subsequence need not be consecutive terms of the original sequence.
Example subsequence
Subsequences of "abc"
= "a"
, "b"
, "c"
, "ab"
, "ac"
, "bc"
and "abc"
.
LCS examples
LCS( "abcdef" , "abc" ) => returns "abc"
LCS( "abcdef" , "acf" ) => returns "acf"
LCS( "132535365" , "123456789" ) => returns "12356"
Notes
- Both arguments will be strings
- Return value must be a string
- Return an empty string if there exists no common subsequence
- Both arguments will have one or more characters (in JavaScript)
- All tests will only have a single longest common subsequence. Don't worry about cases such as
LCS( "1234", "3412" )
, which would have two possible longest common subsequences:"12"
and"34"
.
Note that the Haskell variant will use randomized testing, but any longest common subsequence will be valid.
Note that the OCaml variant is using generic lists instead of strings, and will also have randomized tests (any longest common subsequence will be valid).
Tips
Wikipedia has an explanation of the two properties that can be used to solve the problem:
Strings
Algorithms
Similar Kata:
Stats:
Created | Nov 2, 2013 |
Published | Nov 2, 2013 |
Warriors Trained | 27515 |
Total Skips | 8630 |
Total Code Submissions | 70537 |
Total Times Completed | 6943 |
JavaScript Completions | 2040 |
CoffeeScript Completions | 68 |
Haskell Completions | 453 |
Python Completions | 2557 |
Ruby Completions | 420 |
Java Completions | 1239 |
OCaml Completions | 36 |
Go Completions | 326 |
Total Stars | 728 |
% of votes with a positive feedback rating | 87% of 887 |
Total "Very Satisfied" Votes | 691 |
Total "Somewhat Satisfied" Votes | 153 |
Total "Not Satisfied" Votes | 43 |