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

张开发
• 2026/4/18 5:44:15 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

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 2class 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]

更多文章