网站开发项目章程示例,做网站个体户执照,培训网站推荐,WordPress自媒体MNews给定两个字符串 text1 和 text2#xff0c;返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 #xff0c;返回 0 。
一个字符串的 子序列 是指这样一个新的字符串#xff1a;它是由原字符串在不改变字符的相对顺序的情况下删除某些字符#xff08;也可以…给定两个字符串 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 仅由小写英文字符组成。
总结如果需要确定 保证某种次序就需要确定以....结尾的序列。
//如果 许需要保证 答案序列 需要维持 顺序只要符合条件就可以加进去的。定义为 在0-i区间的字符串是否符合。
class Solution {
public:int longestCommonSubsequence(string text1, string text2) {//求递增序列的时候因为要求序列有序所以必须确定序列最后一个元素的值才能比较新加入序列的元素是不是递增的。求相等序列的时候如果求连续相等子序列则还是要确定序列最后一个元素的值但是本题求的是不必连续的相等子序列就不需要知道序列最后一个元素的值只要知道范围内相等的序列长度就行新来的相等元素可以直接加在序列后面。//dp[i][j]:长度为0- i-1 的text1的字符串 和 长度为0- j-1的text2字符串的最长公共子序列长度为 dp[i][j] 还是从1开始方便初始化//递推关系如果 t1[i-1] t2[i-1] 那么 dp[i][j] dp[i-1][j-1]1;//如果 ! 那么 dp[i][j] max(dp[i-1][j], dp[i][j-1])。继承t1的上一个 和t2的上一个 的最大值 t1 abcde // t2 ace c和e不相等那么可以从 t1中的 abc 和 t2的ac找。也可以从t2的ace 和 t1中的 ac找//初始化考虑 dp[i][0] dp[0][j] 0-1已经越界了可以理解为t1字符串 和空字符串的交集为0。所以第一行和第一列都为0。因此其他所有行都可以为0因为会被覆盖vectorvectorintdp(text1.size()1,vectorint(text2.size()1,0));for(int i 1;i text1.size();i){for(int j 1;j text2.size();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[text1.size()][text2.size()];}
};
