Longest Common Subsequence

1143. 最长公共子序列

分析

定义状态：
- f[i][j] 表示字符串 text1 的前 i 个字符与 text2 的前 j 个字符的最长公共子序列的长度
状态转移：
- 当 text1[i-1] == text2[j-1]，当前字符匹配，可以延续公共子序列的长度：f[i][j] = f[i-1][j-1] + 1
- 当 text1[i-1] != text2[j-1]，当前字符不匹配，最长公共子序列取决于舍弃其中一个字符的结果：f[i][j] = \max(f[i-1][j], f[i][j-1])
边界条件：
- f[i][0] = 0 和 f[0][j] = 0，表示任意一个字符串与空字符串的最长公共子序列长度为 0
结果：
- 最终结果存储在 f[n][m]，其中 n 和 m 分别是 text1 和 text2 的长度

时间复杂度

外层循环遍历 n，内层循环遍历 m ，时间复杂度为 O(nm)

空间复杂度

空间复杂度为 O(nm)

C++代码

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


class Solution
{
public:
    int longestCommonSubsequence(string text1, string text2)
    {
        int n = text1.size(), m = text2.size();
        std::vector<std::vector<int>> f(n + 1, std::vector<int>(m + 1));

        // 遍历每个字符的组合
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= m; ++j)
            {
                f[i][j] = std::max(f[i][j - 1], f[i - 1][j]);
                // 两个字符匹配时
                if (text1[i - 1] == text2[j - 1])
                    f[i][j] = std::max(f[i][j], f[i - 1][j - 1] + 1);
            }

        // 返回最终结果
        return f[n][m];
    }
};