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 &nbsp;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