# LeetCode.1143.Longest Common Subsequence 最长公共子序列LCS

## 题目描述

1143 Longest Common Subsequence
https://leetcode-cn.com/problems/longest-common-subsequence/

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

A subsequence of a string is a new string generated from the original string with some characters(can be none) deleted without changing the relative order of the remaining characters. (eg, “ace” is a subsequence of “abcde” while “aec” is not). A common subsequence of two strings is a subsequence that is common to both strings.

If there is no common subsequence, return 0.

Example 1:

Input: text1 = "abcde", text2 = "ace"
Output: 3
Explanation: The longest common subsequence is "ace" and its length is 3.


Example 2:

Input: text1 = "abc", text2 = "abc"
Output: 3
Explanation: The longest common subsequence is "abc" and its length is 3.


Example 3:

Input: text1 = "abc", text2 = "def"
Output: 0
Explanation: There is no such common subsequence, so the result is 0.


Constraints:
1 <= text1.length <= 1000
1 <= text2.length <= 1000
The input strings consist of lowercase English characters only.

## 解题过程

lcs[i,j] 是序列 Xi=<x1, x2, …, xi>Yj=<y1, y2, …, yj> 的最长公共子序列的长度，则有

$$lcs[i,j] = \begin{cases} 0, & \text{if i = 0 or j = 0 } \\ cls[i-1, j-1] + 1, & \text{if i,j > 0 and x_i = y_j } \\ max(cls[i-1][j], cls[i][j-1]), & \text{if i,j > 0 and x_i \neq y_j } \end{cases}$$

private static class SolutionV2020 {
public int longestCommonSubsequence(String text1, String text2) {
if (null == text1 || text1.length() == 0 || null == text2 || text2.length() == 0) {
return 0;
}
// lcs[i][j] 表示 text1[0...i-1] 和 text2[0...j-1] 的最长公共子序列的长度
int[][] lcs = new int[text1.length() + 1][text2.length() + 1];
// lcsStr[i][j] 表示 text1[0...i-1] 和 text2[0...j-1] 的最长公共子序列
String[][] lcsStr = new String[text1.length() + 1][text2.length() + 1];
for (int i = 0; i <= text1.length(); i++) {
for (int j = 0; j <= text2.length(); j++) {
if (i == 0 || j == 0) {
lcs[i][j] = 0;
lcsStr[i][j] = "";
continue;
}
if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
lcs[i][j] = lcs[i - 1][j - 1] + 1;
lcsStr[i][j] = lcsStr[i - 1][j - 1] + text1.substring(i - 1, i);
} else {
lcs[i][j] = Math.max(lcs[i - 1][j], lcs[i][j - 1]);
lcsStr[i][j] = lcs[i - 1][j] > lcs[i][j - 1] ? lcsStr[i - 1][j] : lcsStr[i][j - 1];
}
}
}
System.out.println(lcsStr[text1.length()][text2.length()]);
return lcs[text1.length()][text2.length()];
}
}


## GitHub代码

algorithms/leetcode/leetcode/_1143_LongestCommonSubsequence.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_1143_LongestCommonSubsequence.java

622

#### 页面信息

location:
protocol:
host:
hostname:
origin:
pathname:
href:
document:
referrer:
navigator:
platform:
userAgent: