This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

1. Title Description

2. How to solve the problem

1. Dynamic planning

The longest common subsequence is a very classical two – dimensional dynamic programming problem. When it comes to dynamic programming, you need to initialize the boundary plus find the state transition equation.

State transition equation

Define a two-dimensional DP array where dp[I][j] represents the length of the longest common subsequence of Text1 [0: I] and Text2 [0:j]. If I >0 and j>0, dp[I +1][j+1] is calculated.

  • Text1 [I +1]==text2[j+1];
dp[i][j] = dp[i-1][j-1]+1
Copy the code
  • 2.text1[i+1]! =text2[j+1], the length of the longest common subsequence does not increase. Its value is derived from existing data.
The length of the longest common subsequence of dp[i-1][j] text1[0:i-1] and text2[0:j-1] should be the maximum length of the longest common subsequence: Max (dp [j], [I - 1] dp [I] [j - 1))Copy the code

Thus, the state transition equation can be obtained:

Boundary initialization

Dp [I][0],dp[0][j] If 0 represents the first string of the string, then loop through the set value.

We can omit the initial assignment by defining 0 as an empty string, because the longest common subsequence of null characters is 0.

Therefore, it can be obtained:

Time complexity analysis

Suppose m and n are the lengths of the strings text1 and text2, respectively. The two-dimensional array DP has m+1 rows and N +1 columns, and each element in DP needs to be evaluated. However, since the boundary does not need to be calculated, the time complexity is:

  • O(nm)

Spatial complexity analysis

Suppose m and n are the lengths of the strings text1 and text2, respectively. Because we need to create an array of (m+1)*(n+1), the space complexity is:

  • O((n+1)(m+1))

Three, code implementation

class Solution { public int longestCommonSubsequence(String text1, String text2) { int m = text1.length(), n = text2.length(); int[][] dp = new int[m + 1][n + 1]; for (int i = 1; i <= m; i++) { char c1 = text1.charAt(i - 1); for (int j = 1; j <= n; j++) { char c2 = text2.charAt(j - 1); if (c1 == c2) { 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[m][n]; }}Copy the code

I don’t know if I have made myself clear, please give me more advice. Punch out for the day!