LeetCode热题100-最长公共子序列

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

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

• 例如，"ace"是"abcde"的子序列，但"aec"不是"abcde"的子序列。

两个字符串的公共子序列是这两个字符串所共同拥有的子序列。

首先明确概念字串是连续的字符，子序列是不保证连续，但是保证前后顺序。经典二维 DP 题，

核心思路

• 状态：dp[i][j]表示text1[0..i-1]和text2[0..j-1]的最长公共子序列长度
• 转移：
  • 字符相等：dp[i][j] = dp[i-1][j-1] + 1
  • 不等：dp[i][j] = max(dp[i-1][j], dp[i][j-1])

空 a c 空 0 0 0 a 0 1 1 b 0 1 1 c 0 1 2

class Solution: def longestCommonSubsequence(self, text1: str, text2: str) -> int: m = len(text1) n = len(text2) dp = [[0] * (n + 1) for _ in range(m + 1)] for i in range(1, m + 1): for j in range(1, n + 1): if text1[i -1] == text2[j - 1]: dp[i][j] = dp[i -1][j - 1] + 1 else: dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) return dp[m][n]