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.

相似题目

LeetCode.1143.Longest Common Subsequence 最长公共子序列LCS LeetCode.718.Maximum Length of Repeated Subarray 最长公共子串/最长重复子数组 LeetCode.300.Longest Increasing Subsequence 最长上升子序列LIS

解题过程

注意区分 最长公共子序列 Longest Common Substring 和 最长公共子串 Longest Common Subsequence，子序列 Subsequence 不要求连续，子串 Substring 必须是连续的。

设 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} $$

时间复杂度 O(mn)，空间复杂度 O(mn)

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