个人网站备案的好处,wordpress打赏作者插件,怎样在网上推广,xd怎么做网页1143. 最长公共子序列#xff08;leetcode#xff09;
题目描述 给定两个字符串 text1 和 text2#xff0c;返回这两个字符串的最长公共子序列的长度。如果不存在公共子序列 #xff0c;返回 0 。一个字符串的子序列是指这样一个新的字符串#xff1a;它是由原字符串在不…1143. 最长公共子序列leetcode
题目描述 给定两个字符串 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 1000 text1 和 text2 仅由小写英文字符组成。 题解1C版本
class Solution {
public:int longestCommonSubsequence(string text1, string text2) {int m text1.size(), n text2.size();int dp[m 1][n 1];memset(dp, 0, sizeof dp);for(int i 1; i m; i){if(text1[i - 1] text2[0]) dp[i][1] 1;else dp[i][1] dp[i - 1][1];}for(int j 1; j n; j){if(text2[j - 1] text1[0]) dp[1][j] 1;else dp[1][j] dp[1][j - 1];}for(int i 2; i m; i){for(int j 2; j n; 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]);}}return dp[m][n];}
};
