logo Practice-It logo

longestCommonSubsequence

Language/Type: Java recursion recursive backtracking
Author: Marty Stepp (on 2012/02/15)

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("ACGGTGTCGTGCTA", "CGTTCGGCTATCGTACGT") "CGGTTCGTGT"

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. The pseudo-code algorithm for finding common subsequences is the following:

longest-common-subsequence(s1, s2):

  • If the strings begin with the same letter c, the result to return is c plus the longest common subsequence between the rest of s1 and s2 (that is, s1 and s2 without their first letter). For example, the longest subsequence between "hollow" and "hello" is an "h" plus the longest subsequence found between "ollow" and "ello".
  • Otherwise, if the strings do not begin with the same letter, return the longer of the following two:
    • The longest common subsequence between s1 and the rest of s2 (s2 without its first letter),
    • The longest common subsequence between the rest of s1 (s1 without its first letter) and s2.
    For example, longest-common-subsequence("ollow", "ello") is the longer of longest-common-subsequence("ollow", "llo") and longest-common-subsequence("llow", "ello").
Type your solution here:


This is a method problem. Write a Java method as described. Do not write a complete program or class; just the method(s) above.

You must log in before you can solve this problem.


Log In

If you do not understand how to solve a problem or why your solution doesn't work, please contact your TA or instructor.
If something seems wrong with the site (errors, slow performance, incorrect problems/tests, etc.), please

Is there a problem? Contact a site administrator.