Practice-It

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.

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").