Write a recursive method longestCommonSubsequence that accepts two strings as parameters and uses recursive backtracking to determine and return the longest common subsequence of characters that appear in both strings. A common subsequence is defined as a sequence of characters that appear in both strings in the same relative order. For example, given the two strings "ABCDEFG" and "BGCEHAF", the longest subsequence between them is "BCEF" because those characters "B", "C", "E", and "F" appear in both strings in the same relative order. The characters in the subsequence need not occur consecutively, and they do not have to occur at the same indexes within the two strings.
If the two strings have no characters in common, or if either string is an empty string, "" should be returned.
Here are some calls to your method and their expected return values.
| Call |
Value Returned |
longestCommonSubsequence("ABCDEFG", "BGCEHAF")
|
"BCEF"
|
longestCommonSubsequence("she sells", "seashells")
|
"sesells"
|
longestCommonSubsequence("12345", "54321 21 54321")
|
"123"
|
longestCommonSubsequence("supercilious teacher", "delicious peach")
|
"ecious each"
|
longestCommonSubsequence("Marty", "Helene")
|
""
|
longestCommonSubsequence("", "Joe")
|
""
|
longestCommonSubsequence("Suzy", "")
|
""
|
longestCommonSubsequence("ACGGTGTCGTGCTTA", "CGTTCGGCTATCGTACGTT")
|
"CGGTTCGTGTTA"
|
Looking for common subsequences is an important algorithm in computer science, from analyzing genetic data (looking for common DNA or proteins) to comparing text files for similarities and differences (as done by our course web site's Output Comparison Tool and the Unix diff command).
Do not use any loops in solving this problem.
