当前位置：网站首页>leetcode 1143. Longest common subsequence (medium)

leetcode 1143. Longest common subsequence (medium)

2022-06-27 00:59:00 【InfoQ】

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];
 }
}