最长公共子序列（LCS）长度

Longest Common Subsequence

专题: Algorithmic Programming / 算法编程
难度: L4
来源: QuantQuestion

题目详情

给定两个字符串 text1 与 text2，返回它们的最长公共子序列（LCS）的长度；若不存在则返回 0。

子序列指删除若干字符但保持相对顺序不变得到的序列。

Given two strings text1 and text2, return the length of the longest common subsequence between the two strings if one exists, otherwise return 0.

A subsequence is a sequence that can be derived from the given sequence by deleting some or no elements without changing the relative order of the remaining characters.

For example, "cat" is a subsequence of "crabt". A common subsequence of two strings is a subsequence that exists in both strings.

Example 1:

Input: text1 = "cat", text2 = "crabt"

Output: 3 Explanation: The longest common subsequence is "cat" which has a length of 3.

Example 2:

Input: text1 = "abcd", text2 = "abcd"

Output: 4 Example 3:

Input: text1 = "abcd", text2 = "efgh"

Output: 0 Constraints:

1 <= text1.length, text2.length <= 1000 text1 and text2 consist of only lowercase English characters.

解析

用动态规划：设 $dp[i][j]$ 为 text1 前 $i$ 个字符与 text2 前 $j$ 个字符的 LCS 长度。

若 text1[i-1]==text2[j-1]： $dp[i][j]=dp[i-1][j-1]+1$ 。
否则： $dp[i][j]=\max(dp[i-1][j],dp[i][j-1])$ 。

答案为 $dp[n][m]$ 。

Original Explanation


class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        memo = {}

        def dfs(i, j):
            if i == len(text1) or j == len(text2):
                return 0
            if (i, j) in memo:
                return memo[(i, j)]
            
            if text1[i] == text2[j]:
                memo[(i, j)] = 1 + dfs(i + 1, j + 1)
            else:
                memo[(i, j)] = max(dfs(i + 1, j), dfs(i, j + 1))
                
            return memo[(i, j)]
        
        return dfs(0, 0)