Longest common subsequence

1. Problem description

For string X=<x1,x2…,xm>, Y=<y1,y2…,yn>, find the longest common subsequence $

2. Solving algorithm

2.1 Brute force cracking

$Assuming that m<n, 2^m-1 subsequences can be found for the parent string X, and then matched in the parent string Y in turn, the time complexity of the algorithm will reach an exponential order O(n * 2^m)$

2.2 Dynamic programming

Optimal substructure: $Suppose Z=< Z1, Z2…, Zk > is the LCS of XX and YY, we observe $

  • $if xm=yn, then zk=xm=yn, then zk −1 is the LCS of xm −1 and yn −1; $
  • $If xm≠yn, then Zk is the LCS of xm and yn −1, or the LCS of xm −1 and yn. $

Therefore, the problem of solving the LCS becomes two subproblems of recursive solution. However, in the above recursive solution method, there are many repeated subproblems and the efficiency is low. The improved method — with space for time, with an array to save the intermediate state, convenient behind the calculation, this is the core idea of dynamic programming (DP). The LCS length of the strings X1X2… Xi and Y1Y2… Yj is recorded by the two-dimensional array Ci, then the state transition equation can be obtained

State transition equation

Recursive implementation of Java code 

public static int lcs(String s1, String s2) {
  char[][] c = new char[s1.length() + 1][s2.length() + 1];
  for (int i = 1; i <= s1.length(); i++) {
    c[i][0] = s1.charAt(i - 1);
  }
  for (int j = 1; j <= s2.length(); j++) {
    c[0][j] = s2.charAt(j - 1);
  }
  return recursion(c, s1.length(), s2.length());
}
public static int recursion(char[][] c, int i, int j) {
  if (i == 0 || j == 0) {
    return 0;
  }
  if (c[i][1] == c[1][j]) {
    return recursion(c, i - 1, j - 1) + 1;
  } 
  return Math.max(recursion(c, i, j - 1), recursion(c, i - 1, j));
}

Java code dynamically plans the implementation from the bottom up 

public static int lcs(String s1, String s2) { char[][] c = new char[s1.length() + 1][s2.length() + 1]; int[][] dp = new int[s1.length() + 1][s2.length() + 1]; // for (int I = 1; i <= s1.length(); i++) { c[i][0] = s1.charAt(i - 1); } for (int j = 1; j <= s2.length(); j++) { c[0][j] = s2.charAt(j - 1); } // initialize dp for (int I = 0; i <= s1.length(); i++) { dp[i][0] = 0; } for (int j = 0; j < s2.length(); j++) { dp[0][j] = 0; } for (int I = 1; i <= s1.length(); i++) { for (int j = 1; j <= s2.length(); j++) { if (c[i][0] == c[0][j]) { dp[i][j] = dp[i - 1][j - 1] + 1; } else { dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); } } } return dp[s1.length()][s2.length()]; }

The longest common subsequence and the longest common subsequence dynamic programming process diagram of the longest common subsequence dynamic programming solution of the longest common subsequence (LCS)(with a detailed process of filling the table