Leetcode 1143. 最长公共子序列

地址：https://leetcode-cn.com/problems/longest-common-subsequence

题目

给定两个字符串 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
• 输入的字符串只含有小写英文字符。

解题思路

这个题并不是我自己做的，是我在学习动态规划的过程中看到的 Leetcode 官方的一篇关于动态规划的文章：算法萌新如何学好动态规划（2），觉得这个题目的解题思路很有意思，所以记录一下~

关于具体的解题思路以及状态转移方程这里不做过多描述了，可以参考原文解题思路。

我觉得很有意思的一个地方是，请看下方代码，按理说我们一般会用一个 n × m 的矩阵用于存储 f[i][j] 的值，即第一个串的前 i 个字符与第二个串的前 j 个字符的最长公共子序列长度，而代码第 5 行却初始化了一个全零的 n+1 × m+1 矩阵，至少我看到这里的时候是有疑惑的，而我最初想到的原因也只是为了理解上更加直观，当然这可以说是一个原因，但事实上这不是最主要的原因。

继续看代码，到第 8 行就明白了，涉及到了对索引 i - 1 、 j - 1 的取值，由于 0 行 0 列根本用不到，而 i 、 j 的初始值均为 1 ，也就是说我们无需再对边界值进行特殊处理，并且将矩阵初始化为全 0 也是有意义的，例如 f[1][1] 就可以直接由 max(f[0][1], f[1][0]) 得到。简言之，对于我们想要得到的这个 n × m 的矩阵，就不需要处理任何的特殊情况了，实在是很方便~

当然上面这些更多的是“取巧”，这个题最核心的部分还是怎么得到它的状态转移方程。

代码

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int n = text1.length(), m = text2.length();
        vector<vector<int> > f(n+1, vector<int>(m+1, 0));
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= m; j++) {
                f[i][j] = max(f[i-1][j], f[i][j-1]);
                if(text1[i-1] == text2[j-1])
                    f[i][j] = max(f[i][j], f[i-1][j-1]+1);
            }
        }
        return f[n][m];
    }
};