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

First, the topic overview

LeetCode 1143. Longest common subsequence

Given two strings text1 and text2, return the length of the longest common subsequence of the two strings.

A subsequence of a string is a new string made up of the original string without changing the relative order of the characters by deleting some characters (or none).

For example, “ace” is a subsequence of “ABCDE”, but “AEC” is not a subsequence of “ABCDE”. A “common subsequence” of two strings is a subsequence that is shared by both strings.

Returns 0 if the two strings have no common subsequence.

Example 1: Input: text1 = "abcde", text2 = "ace" Output: 3 Explanation: The longest common subsequence is "ace", which has length 3. Example 2: Input: text1 = "ABC ", text2 =" ABC "Output: 3 Explanation: The longest common subsequence is" ABC ", which has length 3. Example 3: Input: text1 = "ABC ", text2 = "def" Output: 0 Explanation: The two strings have no common subsequence, return 0.Copy the code


Dry problem analysis

** Longest Common Subsequence (LCS) ** is a very classic interview topic, because its solution is a typical two-dimensional dynamic programming.

This algorithm can be modified to solve other problems, so the LCS algorithm is worth learning.

Dynamic planning idea:

  1. Step 1: Be specificdpThe meaning of array
  2. definebase case
  3. Find the state transition equation


Step 1: Be specificdpThe meaning of array.

For the dynamic programming problem of two strings, the routine is general, generally requires a two-dimensional DP array.

For example, for strings s1 and s2, we typically construct a DP table like this:

For s1[0.. i-1] and S2 [0.. j-1], their LCS length is DP [I][j].

For example, dp[2][4] = 2 means that for “ac” and “babc”, their LCS length is 2. According to this definition, the final desired answer should be DP [3][6].


Definition 2.base case

Specify rows and columns with index 0 to represent empty strings, dp[0][..] And dp […] [0] should all be initialized to 0, that’s the base case.

For example, dp[0][3] = 0 means that the LCS of the empty strings “” and “bab” is 0.

Since one of the strings is an empty string, the length of their longest common subsequence should obviously be 0


3. Find the state transition equation

Make choices.

Find the longest common subsequence of S1 and S2, and let the subsequence be LCS.

So what are the choices for each character in S1 and S2?

Very simple, two choices, either in the LCS or not.

As shown in figure:

For s1[I] and S2 [j], how do I know if they are in the LCS?

It’s easy to imagine that if a character is in LCS, it must be in both S1 and S2, because LCS is the longest common subsequence.

Dp (I, j) represents the length of the longest common subsequence in S1 [0… I] and S2 [0…j], so that the state transition relation can be found:

  1. ifs1[i] == s2[j]

If you know the length of the LCS in s1[0.. I] and S2 [0..j-1], add 1 to the length of the LCS in S1 [0.. I] and S2 [0..j]. According to the definition of dp function, as follows:

if (str1[i] == str2[j]) dp[i][j] = dp(i - 1, j - 1) + 1;
Copy the code
  1. ifs1[i] ! = s2[j]

At least one of the characters s1[I] and S2 [j] is not in the LCS. According to the definition of dp function, as follows:

if (str1[i] ! = str2[j]) dp[i][j] = Math.max(dp(i - 1, j), dp(i, j - 1));Copy the code

If you understand the state transition equation, you can just write down the solution.





Second, the idea of implementation

Ideas:

  1. 2 d arraydp
  2. dpThe compression
public class LeetCode_1143 {
    / / Time: O (n ^ 2), Space: O (m * n), Faster - : 72.28%
    public int longestCommonSubsequence(String text1, String text2) {

        int m = text1.length(), n = text2.length();
        / / definition: for s1 and s2 [0.. I - 1] [0.. 1] j, they are the length of dp [I] [j].
        // base case: dp[0][..]  = dp[..] [0] = 0 initialized
        int [][] dp = new int[m + 1][n + 1];

        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                // State transition logic
                if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]); }}}returndp[m][n]; }}Copy the code