题目浅析

  • 想查看原题可以点击题目链接。

  • 简单地说，就是找到两个字符串的最长公共子序列（具体含义请看原题）长度。

思路分享

  • 这是线性 DP 的经典题目，子序列由于是可以选择性的删除中间部分，所以计算两个字符串的公共子序列，可以分为多个子问题，具体分析如下：

    https://leetcode.cn/problems/longest-common-subsequence/solutions/2133188/jiao-ni-yi-bu-bu-si-kao-dong-tai-gui-hua-lbz5/

  • 对于两个字符串，每分别选的两个字符各有选和不选两种情况，也就是四种情况。在相等的情况下，肯定是两个都选好；不等时则两边各选一次。两边都不选一定不如上面三种情况。

  • 比如，有长 n、m 的两个字符串的最长公共子序列就是下面的子情况推导出来的：1. n-1、m；2. n、m-1；3. n-1、m-1. 前两个是字符匹配失败的场景，3 是字符相等的场合

代码解答（强烈建议自行解答后再看）

  • 参考题解
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
26
27
28
29
30
class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        n = len(text1)
        m = len(text2)

        f = [0] * (m+1)
        
        for i, x in enumerate(text1):
            pre = f[0]
            for j, y in enumerate(text2):
                tmp = f[j+1]
                if x == y:
                    f[j+1] = pre + 1
                else:
                    f[j+1] = max(f[j], f[j+1])
                pre = tmp
        
        return f[m]

        # @cache
        # def dfs(i:int, j:int) -> int:
        #     if i < 0 or j < 0:
        #         return 0

        #     if text1[i] == text2[j]:
        #         return dfs(i-1, j-1) + 1
            
        #     return max(dfs(i-1, j), dfs(i, j-1))
        
        # return dfs(n-1, m-1)