最长公共子序列

题目描述

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

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

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

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

来源：LeetCode

解法一

动态规划思想的本质是动态表格(dynamic table)，使用动态规划必须满足两个条件：1.重复子问题，2.最优子结构，表格的思想是以空间换时间，把求解的所有子问题的解都保存下来，不用重复计算，最优子结构则保证了，原问题的解由子问题的组合构成，就可以写成递推公式，在较短的时间复杂度内求解。
针对LCS问题，把字符串a表示为(X1,X2,…,Xm)，字符串b表示为(Y1,Y2,…,Yn)，我们先看看能不能划分子问题：求a和b的LCS，可以定义为LCS[i,j]，其中i表示从X1到Xi的子串，j表示从Y1到Yj的子串，这里固定了字符串的起始索引1。为什么这么划分子问题？因为如果起始索引和结束索引都动态的话，那就更难解决了，更重要的是，我们求最长公共子序列，起始索引动态是没有意义的，因为起始索引大于1的子问题，其结果总会小于等于索引为1的子问题结果。
问题形式化之后，我们发现，如果Xi=Yj，则LCS[i,j]=LCS[i-1,j-1]+1，只需要再考虑LCS[i-1,j-1]这个子问题，如果不相等，则有两个子问题需要解决，LCS[i,j]=max(LCS[i,j-1], LCS[i-1,j])，如果i=0或j=0，说明有一个字符串已经结束了，则LCS[i,j]=0

解决递推公式问题，有两种方法，一种是自底向上，从求解小问题开始，逐渐求解整个问题，另一种是递归的方式，因为中途有很多重复子问题（如LCS[i-1,j-1]可能是LCS[i,j]的子问题，也可能LCS[i,j-1]的子问题），所以使用memo数组记录下这些子问题的解。

以下是递归+memo的解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int size1 = text1.size();
        int size2 = text2.size();
        int memo[1001][1001];
        for(int i = 0; i < 1001; i++) {
            for(int j = 0; j < 1001; j++) {
                memo[i][j] = -1;
            }
        }
        return lcs(text1, text2, memo, size1-1, size2-1);
    }
    int lcs(string & a, string & b, int memo[][1001], int i, int j) {
        if(i == -1 || j == -1) return 0; // 有一个字符串已经结束
        if(memo[i][j] != -1) return memo[i][j];
        if(a[i] == b[j]) {
            memo[i][j] = lcs(a, b, memo, i-1, j-1) + 1;
            return memo[i][j];
        } else {
            memo[i][j] = max(lcs(a, b, memo, i-1, j), lcs(a, b, memo, i, j-1));
            return memo[i][j];
        }
    }
};

解法二

自底向上的解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int dp[1001][1001];
        // 对于dp数组的初始化
        // memset更高效 memset针对cpu指令集做了优化
        memset(dp, 0, 1001*1001*sizeof(int));
        int size1 = text1.size();
        int size2 = text2.size();
        for(int i = 1; i <= size1; i++) {
            for(int j = 1; j <= size2; j++) {
                if(text1[i-1] == text2[j-1]) {
                    dp[i][j] = dp[i-1][j-1] + 1;
                } else {
                    dp[i][j] = max(dp[i][j-1], dp[i-1][j]);
                }
            }
        }
        return dp[size1][size2];
    }
};