LeetCode热题100 最长公共子序列

张开发
• 2026/5/2 21:24:43 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

LeetCode热题100 最长公共子序列
题目描述给定两个字符串 text1 和 text2返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 返回 0 。一个字符串的 子序列 是指这样一个新的字符串它是由原字符串在不改变字符的相对顺序的情况下删除某些字符也可以不删除任何字符后组成的新字符串。例如“ace” 是 “abcde” 的子序列但 “aec” 不是 “abcde” 的子序列。两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。示例 1输入text1 “abcde”, text2 “ace”输出3解释最长公共子序列是 “ace” 它的长度为 3 。示例 2输入text1 “abc”, text2 “abc”输出3解释最长公共子序列是 “abc” 它的长度为 3 。示例 3输入text1 “abc”, text2 “def”输出0解释两个字符串没有公共子序列返回 0 。提示1 text1.length, text2.length 1000text1 和 text2 仅由小写英文字符组成。思路动态规划板子详细转移方程和状态表示见代码。代码classSolution{public:intlongestCommonSubsequence(string text1,string text2){intntext1.length(),mtext2.length();// 考虑text1以(1, i), text2以(1, j)的答案最大值vectorvectorintdp(n1,vectorint(m1,0));for(inti1;in;i){for(intj1;jm;j){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]);}}}returndp[n][m];}};

更多文章