(DP review)Longest Common Substring, Longest Common Subsequence

1.Find the longest common substring of two given strings.

Assumptions

  • The two given strings are not null

Examples

  • S = “abcde”, T = “cdf”, the longest common substring of S and T is “cd”

My solution:

This problem could be resolved by maintaining a 2D array ,which could be expressed as M[][]=new M[S.length()][T.length()];the value of each indice of M, M[i][j] records the length of the longest common substring of the substring of S(from 0 to i) and the substring of T(from 0 to j).The string S and T from above examples could be expressed as the 2D array below:

….c….d….f

a…0….0….0

b….0….0….0

c…..1….0….0

d….0…..2….0

e…..0…..0…..0

From the array above, we could easily write the code for this problem.

Here is my Java solution:

public String longestCommon(String s, String t) {
 if(s.length() == 0 || t.length() == 0){
 return “”;
 }
 int[][]M=new int[s.length()][t.length()];
 int max=0;
 int indice=0;
 for(int i=0; i<s.length(); i++){
 for(int j=0; j<t.length(); j++){
 if(s.charAt(i) == t.charAt(j)){
 if(i == 0 || j == 0){
 M[i][j]=1;
 }else{
 M[i][j]=M[i-1][j-1]+1;
 }
 }else{
 M[i][j]=0;
 }
 if(M[i][j] > max){
 max=M[i][j];
 indice=i;
 }
 }
 }
 return s.substring(indice-max+1,indice+1);
 }

2.Find the length of longest common subsequence of two given strings.

Assumptions

  • The two given strings are not null

Examples

  • S = “abcde”, T = “cbabdfe”, the longest common subsequence of s and t is {‘a’, ‘b’, ‘d’, ‘e’}, the length is 4.

This question is similar as above, the main idea is also using a 2D array to record the states. But the difference is that since this time we need to find the longest common subsequence. By using the trick of “add one” as above, the problem could be easily handeled. Each indice M[i][j] represents the length longest common subsequence of the substring of s from 0 to i and the substring of t from 0 to j.

The example above could be expressed as:

..a….b….c….d….e

c..0….0…1….1…..1

b…0…1….1….1….1

a…1…1….1…..1…..1

b….1…2….2…..2….2

d….1….2….2….3….3

f…..1….2…..2….3….3

e….1….2…..2…..3….4

We just need to find the last value in this array to get the result. In this case, the result is 4.

Here is my Java solution:

public int longest(String s, String t) {
 int[][] longest =new int[s.length()+1][t.length()+1];
 for(int i=1; i<=s.length(); i++){
 for(int j=1; j<=t.length(); j++){
 if(s.charAt(i-1) == t.charAt(j-1)){
 longest[i][j]=longest[i-1][j-1]+1;
 }else{
 longest[i][j]=Math.max(longest[i-1][j],longest[i][j-1]);
 }
 }
 }
 return longest[s.length()][t.length()];
 }