Ricky.L的随笔
0%

LeetCode.1143.最长公共子序列（中等）

发表于 更新于 分类于 Disqus：

题目

LeetCode.1143.最长公共子序列（中等）

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

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

例如，”ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

题解

解法1：记忆化递归

尝试划分子问题。

如果text1和text2存在公共子序列，那是怎么得来的？
肯定是之前没有公共子序列或者存在公共子序列，然后又发现了两者相同的字符，得到了更长的公共子序列。

如果末尾字符不相同怎么办？

  1. 删除text1的末尾字符，剩余字符串去跟text2比较。
  2. 删除text2的末尾字符，剩余字符串去跟text1比较。

取两种情况中可以得到的最长公共子序列的情况。

同时删除text1和text2的末尾字符要不要考虑？

这里划分出了子问题和所有的递推步骤。

递归

1
2
3
4
5
6
7
8
9
10
class Solution {
    fun longestCommonSubsequence(text1: String, text2: String): Int {
        fun solve(i1: Int, i2: Int): Int {
            if (i1 == -1 || i2 == -1) return 0 
            return if (text1[i1] == text2[i2]) 1 + solve(i1 - 1, i2 - 1)
            else maxOf(solve(i1 - 1, i2), solve(i1, i2 - 1))
        }
        return solve(text1.length - 1, text2.length - 1)
    }
}

存在重叠子问题，有大量重复计算，用数组记录中间计算结果。

记忆化递归

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    fun longestCommonSubsequence(text1: String, text2: String): Int {
        val memo = Array(text1.length) { IntArray(text2.length) { 0 } }
        fun solve(i1: Int, i2: Int): Int {
            if (i1 == -1 || i2 == -1) return 0 
            if (memo[i1][i2] > 0) return memo[i1][i2]
            memo[i1][i2] = if (text1[i1] == text2[i2]) 1 + solve(i1 - 1, i2 - 1)
            else maxOf(solve(i1 - 1, i2), solve(i1, i2 - 1))
            return memo[i1][i2]
        }
        return solve(text1.length - 1, text2.length - 1)
    }
}

解法2：自底向上动态规划

设dp[i][j]为text1的前i + 1个字符与text2的前j + 1个字符最长公共子序列的长度。

状态转移方程

  • text1[i] == text2[j]时，dp[i][j] = 1 + dp[i - 1][j - 1]
  • text1[i] != text2[j]时，dp[i][j] = maxOf(dp[i - 1][j], dp[i][j - 1])

边界处理
设s1是text1子字符串，s2是text2子字符串。

  • s1和s2为一个字符时，只需要判断字符是否相同，可以计算dp[0][0]。
  • s1只有一个字符时，如果跟s2的字符不相同，s1没办法再删减，直接取s2删减后的结果。
  • s2只有一个字符时，如果跟s1的字符不相同，s2没办法再删减，直接取s1删减后的结果。

复杂度
设text1长度为m，text2长度为n。
时间复杂度O(mn)：双循环无法省略。
空间复杂度O(mn)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    fun longestCommonSubsequence(text1: String, text2: String): Int {
        val n1 = text1.length
        val n2 = text2.length
        val dp = Array(n1) { IntArray(n2) { 0 } }
        dp[0][0] = if (text1[0] == text2[0]) 1 else 0
        for (i in 1 until n1) dp[i][0] = if (text1[i] == text2[0]) 1 else dp[i - 1][0]
        for (j in 1 until n2) dp[0][j] = if (text1[0] == text2[j]) 1 else dp[0][j - 1]
        for (i in 1 until n1) {
            for (j in 1 until n2) {
                dp[i][j] = if (text1[i] == text2[j]) 1 + dp[i - 1][j - 1]
                else maxOf(dp[i - 1][j], dp[i][j - 1])
            }
        }
        return dp[n1 - 1][n2 - 1]
    }
}