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"
lcs "a"         "b"         `shouldBe` ""
lcs "abcdef"    "abc"       `shouldBe` "abc"
lcs "132535365" "123456789" `shouldBe` "12356"
lcs( "abcdef" , "abc" ) => returns "abc"
lcs( "abcdef" , "acf" ) => returns "acf"
lcs( "132535365" , "123456789" ) => returns "12356"
lcs( "abcdef" , "abc" ) => returns "abc"
lcs( "abcdef" , "acf" ) => returns "acf"
lcs( "132535365" , "123456789" ) => returns "12356"
Solution.lcs("abcdef", "abc") => returns "abc"
Solution.lcs("abcdef", "acf") => returns "acf"
Solution.lcs("132535365", "123456789") => returns "12356"
LCS( "abcdef", "abc" ) => returns "abc"
LCS( "abcdef", "acf" ) => returns "acf"
LCS( "132535365", "123456789" ) => returns "12356"
lcs ['a';'b';'c';'d';'e';'f'] ['a';'b';'c'] => returns ['a';'b';'c']
lcs ['a';'b';'c';'d';'e';'f'] ['a';'c';'f'] => returns ['a';'c';'f']
lcs [1;3;2;5;3;5;3;6;5] [1;2;3;4;5;6;7;8;9] => returns [1;2;3;5;6]

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

Stats:

CreatedNov 2, 2013
PublishedNov 2, 2013
Warriors Trained27515
Total Skips8630
Total Code Submissions70537
Total Times Completed6943
JavaScript Completions2040
CoffeeScript Completions68
Haskell Completions453
Python Completions2557
Ruby Completions420
Java Completions1239
OCaml Completions36
Go Completions326
Total Stars728
% of votes with a positive feedback rating87% of 887
Total "Very Satisfied" Votes691
Total "Somewhat Satisfied" Votes153
Total "Not Satisfied" Votes43
Ad
Contributors
  • xDranik Avatar
  • jhoffner Avatar
  • Azuaron Avatar
  • bkaes Avatar
  • GiacomoSorbi Avatar
  • aweleshetu Avatar
  • cacr Avatar
  • jasonwyatt Avatar
  • Voile Avatar
  • scorphus Avatar
  • FArekkusu Avatar
  • monadius Avatar
  • albertogcmr Avatar
  • Just4FunCoder Avatar
Ad