Find the longest common subsequence in two strings

This is classic dynamic programming problem.
Given two strings, find the longest common subsequence in the two strings. For example: input: ABCD and BDACE, output: AC or BC. Note it could have multiple answers, but we only need to output one of them.

In the MIT 6.006 course, the dynamic programming were introduced very nicely in the following steps:
1. define subproblem
2. guess
3. related subproblem solutions
4. recurse + memoize OR build DP table bottom-up
5. solve original problem

So let's use the above technique to solve today's problem. First of all, we can reduce the problem to find the length of the longest common subsequence in two strings. Because once we can do that, we can devise our solution from it. Here are the steps:

1. Subproblem will be DP(i, j) where i, j will be the indices of two strings
2. Guess the choice, the choices from DP(i-1, j-1) or DP(i-1, j) or DP(i, j-1).
3. Recurrence, there are two cases:
    1) char of string1 at index i is the same of char of string2 at index j
        DP(i, j) = DP(i-1, j-1) + 1
    2) not the same
        DP(i, j) = Max(DP(i-1, j), DP(i, j-1))
4. Topological order, thinking about DP as 2D matrix, the order will be from top-left corner (0,0) either going right or going left to the bottom-right corner (lenString1, lenString2).
5. Original problem's solution will be DP (lenString1, lenString2).

And once we compute the DP table, then we can do back-tracing from bottom-right corner to find the longest common subsequence.

Here is the code:

public static String findLongestSubsequence(String s1, String s2){

int len1 = s1.length(), len2 = s2.length();

//part1 build DP table bottom-up

int[][] table = new int[len1+1][len2+1];

for(int i = 0; i<len1+1; i++)

    table[i][0] = 0;

     

for(int i = 0; i<len2+1; i++)

    table[0][i] = 0;

     

for(int i = 1; i<len1+1; i++){

    for(int j=1; j<len2+1; j++){

        if(s1.charAt(i-1) == s2.charAt(j-1))

            table[i][j] = table[i-1][j-1]+1;

        else

            table[i][j] = Math.max(table[i-1][j], table[i][j-1]);         

    }

}    

//part 2 backtracing   

StringBuilder sb = new StringBuilder(); 

int i = len1, j = len2;

while(i>0 && j>0){

    if(s1.charAt(i-1) == s2.charAt(j-1)){

        sb.append(s1.charAt(i-1));

        i--; j--;   

    }else if(table[i][j] == table[i-1][j])

        i--;

    else

        j--;    

}

return sb.reverse().toString();

}

Find Longest Common Subsequence Length of two strings

Problem:
Given two strings: "AGGTAB", "GXTXAYB", find the length of the longest common subsequence.

The answer for the two strings is 4, "GTAB". Note subsequence is the substring of string with the characters appears in the order as they are in the string but not necessary contiguously.

Solution 1. 

Do it recursively

 /* do it recursively

* @param s1

* @param s2

* @return

*/

public static int findLongestCommonSubsequence(String s1, String s2){

if(s1.isEmpty() || s2.isEmpty())

return 0;

String substring1 = s1.substring(0, s1.length()-1);

String substring2 = s2.substring(0, s2.length()-1);

if(s1.charAt(s1.length()-1) == s2.charAt(s2.length()-1)) {

return 1+StringQ.findLongestCommonSubsequence(substring1, substring2);

} else{

return Math.max(StringQ.findLongestCommonSubsequence(s1, substring2), StringQ.findLongestCommonSubsequence(substring1, s2));

}

} 

Solution 2.

Do it iteratively:

       public static int findLongestCommonSubsequence2(String s1, String s2){

char[] cArray1 = s1.toCharArray();

char[] cArray2 = s2.toCharArray();

int[][] lcs = new int[s1.length()+1][s2.length()+1];

for(int i=0; i<cArray1.length; i++){

for(int j=0; j<cArray2.length; j++){

if(cArray1[i] == cArray2[j])

lcs[i+1][j+1] = lcs[i][j] + 1;

else

lcs[i+1][j+1] = Math.max(lcs[i+1][j], lcs[i][j+1]);

}

}

return lcs[s1.length()][s2.length()];

}