1143. 最长公共子序列

leetcode 1143. 最长公共子序列

题目：1143. 最长公共子序列

给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。例如，”ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。

若这两个字符串没有公共子序列，则返回 0。

示例1:

输入：text1 = “abcde”, text2 = “ace”
输出: 3
解释：最长公共子序列是 “ace”，它的长度为 3。

示例2:

输入：text1 = “abc”, text2 = “abc”
输出: 3
解释：最长公共子序列是 “abc”，它的长度为 3。

示例3:

输入：text1 = “abc”, text2 = “def”
输出: 0
解释：两个字符串没有公共子序列，返回 0。

提示:

• 1 <= text1.length <= 1000
• 1 <= text2.length <= 1000
• 输入的字符串只含有小写英文字符。

方法一：动态规划

思路：动态规划。状态转移方程为：dp[i][j] = dp[i - 1][j - 1] + 1;（text1.charAt(i - 1) == text2.charAt(j - 1)）。dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);（text1.charAt(i - 1) != text2.charAt(j - 1)）。dp[i][j]表示text1前i个字符和text2的前j个字符的最长公共子序列。

运行数据：执行用时：12 ms，内存消耗：42.2 MB

复杂度分析：

• 时间复杂度：O(n * m)，n为text1的长度，m为text2的长度。
• 空间复杂度：O(n * m)，n为text1的长度，m为text2的长度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

// LeetCode指定调用方法 
public int longestCommonSubsequence(String text1, String text2) {

    int n = text1.length();
    int m = text2.length();

    int[][] dp = new int[n + 1][m + 1];

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; 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[n][m];
}

方法二：优化动态规划

思路：优化动态规划。在思路一的基础上将dp的二维数组空间消耗，压缩成一维数组。

运行数据：执行用时：11 ms，内存消耗：36.8 MB

复杂度分析：

• 时间复杂度：O(n * m)，n为text1的长度，m为text2的长度。
• 空间复杂度：O(m)，m为text2的长度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

// LeetCode指定调用方法 
public int longestCommonSubsequence(String text1, String text2) {

    int n = text1.length();
    int m = text2.length();

    int[] dp = new int[m + 1];

    int temp1 = 0, temp2 = 0;
    for (int i = 1; i <= n; i++) {
        temp1 = 0;
        for (int j = 1; j <= m; j++) {
            temp2 = dp[j];
            if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                dp[j] = temp1 + 1;
            } else {
                dp[j] = Math.max(dp[j], dp[j - 1]);
            }
            temp1 = temp2;
        }
    }

    return dp[m];
}

学习所得，资料、图片部分来源于网络，如有侵权，请联系本人删除。

才疏学浅，若有错误或不当之处，可批评指正，还请见谅！