Classic DP model: longest common subsequence problem | Java brush problem punch card

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

Topic describes

This is 1143. Longest common subsequence on LeetCode with medium difficulty.

Tag: “longest common subsequence”, “LCS”, “sequence DP”

Given two strings text1 and text2, return the length of the longest common subsequence of the two strings. If no common subsequence exists, return 0.

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.

Example 1:

Input: text1 = "abcde", text2 = "ace" Output: 3 Explanation: The longest common subsequence is "ace", which has length 3.Copy the code

Example 2:

Input: text1 = "ABC ", text2 =" ABC "Output: 3 Explanation: The longest common subsequence is" ABC ", which has length 3.Copy the code

Example 3:

Input: text1 = "ABC ", text2 = "def" Output: 0 Explanation: The two strings have no common subsequence, return 0.Copy the code

Tip:

• 1 <= text1.length, text2.length <= 1000
• Text1 and Text2 consist only of lowercase English characters.

Dynamic programming

This is a naked question on the longest Common subsequence (LCS).

For all these questions, use the following “state definition” :

$f[i][j]$On behalf of the consideration
$s1$The former
$i$A character, consider
$s2$The former
$j$The longest common subsequence length formed by the character.

Once you have a “state definition”, you basically have a “transition equation” :

• s1[i]==s2[j] :
  $f[i][j]=f[i-1][j-1]+1$. On behalf ofMust use
  $s1[i]$ 与
  $s2[j]$ 时The length of the LCS.
• s1[i]! =s2[j] :
  $f[i][j]=max(f[i-1][j], f[i][j-1])$. On behalf ofDefinitely not used
  $s1[i]$(But possible use
  $s2[j]$) 和 Definitely not used
  $s2[j]$(But possible use
  $s1[i]$)The length of the LCS.

Some coding details:

Usually I habitually append a space to the head of the string to reduce margin judgment (make the subscript start at 1 and make it easy to construct scrollable “valid values”).

Code:

class Solution {
    public int longestCommonSubsequence(String s1, String s2) {
        int n = s1.length(), m = s2.length();
        s1 = "" + s1; s2 = "" + s2;
        char[] cs1 = s1.toCharArray(), cs2 = s2.toCharArray();
        int[][] f = new int[n + 1][m + 1]; 

        // Because of the appended space, we have an obvious initialization value (either of the following initialization methods will work)
        // for (int i = 0; i <= n; i++) Arrays.fill(f[i], 1);
        for (int i = 0; i <= n; i++) f[i][0] = 1;
        for (int j = 0; j <= m; j++) f[0][j] = 1;

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (cs1[i] == cs2[j]) {
                    f[i][j] = f[i -1][j - 1] + 1;
                } else {
                    f[i][j] = Math.max(f[i - 1][j], f[i][j - 1]); }}}// Subtract the initial appended space
        return f[n][m] - 1; }}Copy the code

• Time complexity: O(n∗m)O(n * m)O(n∗m)
• Space complexity: O(n∗m)O(n * m)O(n∗m)

Dynamic programming [using migration]

The above “additional space” is my more accustomed to the practice 🤣

In fact, we can also implement recursion by modifying the “state definition” :

$f[i][j]$On behalf of the consideration
$s1$The former
$i – 1$A character, consider
$s2$The former
$j – 1$The longest common subsequence length formed by the character.

So eventually f [n] [m] f [n] [m] f [n] [m] is our answer, f [0] [0] f [0] [0] f [0] [0] as invalid values, not processing.

• s1[i-1]==s2[j-1] :
  $f[i][j]=f[i-1][j-1]+1$. On behalf of the use of
  $s1[i-1]$ 与
  $s2[j-1]$The length that forms the longest common subsequence.
• s1[i-1]! =s2[j-1] :
  $f[i][j]=max(f[i-1][j], f[i][j-1])$. Do not use
  $s1[i-1]$Form the length of the longest common subsequence, not used
  $s2[j-1]$The length that forms the longest common subsequence. The maximum in both cases.

Code:

class Solution {
    public int longestCommonSubsequence(String s1, String s2) {
        int n = s1.length(), m = s2.length();
        char[] cs1 = s1.toCharArray(), cs2 = s2.toCharArray();
        int[][] f = new int[n + 1][m + 1]; 
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (cs1[i - 1] == cs2[j - 1]) {
                    f[i][j] = f[i - 1][j - 1] + 1;
                } else {
                    f[i][j] = Math.max(f[i - 1][j], f[i][j - 1]); }}}returnf[n][m]; }}Copy the code

• Time complexity: O(n∗m)O(n * m)O(n∗m)
• Space complexity: O(n∗m)O(n * m)O(n∗m)

The last

This is the No.1143 of our “Brush through LeetCode” series of articles. The series started on 2021/01/01.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour…

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.