leetcode 1143. Longest common subsequence (medium)

One 、 The main idea of the topic

label : Dynamic programming

https://leetcode.cn/problems/longest-common-subsequence

Given two strings  text1 and  text2, Returns the longest of these two strings Common subsequence The length of . If it doesn't exist Common subsequence , return 0 .

A string of   Subsequence   This is a new string ： It is to delete some characters from the original string without changing the relative order of the characters （ You can also delete no characters ） After the composition of the new string .

for example ,"ace" yes "abcde" The subsequence , but "aec" No "abcde" The subsequence .
Two strings of Common subsequence Is the subsequence shared by these two strings .

Example 1：

Input ：text1 = "abcde", text2 = "ace"
Output ：3
explain ： The longest common subsequence is "ace" , Its length is 3 .

Example 2：

Input ：text1 = "abc", text2 = "abc"
Output ：3
explain ： The longest common subsequence is "abc" , Its length is 3 .

Example 3：

Input ：text1 = "abc", text2 = "def"
Output ：0
explain ： The two strings have no common subsequence , return 0 .

Tips ：

• 1 <= text1.length, text2.length <= 1000
• text1 and  text2 It only consists of lowercase English characters .

Two 、 Their thinking

Use dynamic programming to solve this problem , Define a two-dimensional array dp, among dp[i][j] Indicates to the first string position i until 、 To the second string position j until 、 The longest common subsequence length . In this way, we can easily discuss the cases where the letters corresponding to the two positions are the same or different .

3、 ... and 、 How to solve the problem

3.1 Java Realization

public class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length();
        int n = text2.length();
        //  Indicates to the first string position i until 、 To the second string position j until 、 The longest common subsequence length 
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i < m + 1; i++) {
            for (int j = 1; j < n + 1; j++) {
                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 - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[m][n];
    }
}

Four 、 Summary notes

• 2022/6/26 Tomorrow Monday , Continue refueling