lintcode77. 最长公共子序列

小灰灰 2023-07-03 15:28 4阅读 0赞

给出两个字符串，找到最长公共子序列(LCS)，返回LCS的长度。

样例
    样例 1:
    	输入:  "ABCD" and "EDCA"
    	输出:  1
    	
    	解释:
    	LCS 是 'A' 或  'D' 或 'C'
    
    
    样例 2:
    	输入: "ABCD" and "EACB"
    	输出:  2
    	
    	解释: 
    	LCS 是 "AC"
    说明
    最长公共子序列的定义：
    
    最长公共子序列问题是在一组序列（通常2个）中找到最长公共子序列（注意：不同于子串，LCS不需要是连续的子串）。该问题是典型的计算机科学问题，是文件差异比较程序的基础，在生物信息学中也有所应用。
    https://en.wikipedia.org/wiki/Longest_common_subsequence_problem

class Solution {
        
    public:
        /**
         * @param A: A string
         * @param B: A string
         * @return: The length of longest common subsequence of A and B
         */
        int longestCommonSubsequence(string &A, string &B) {
        
            // write your code here
            int lena=A.size();
            int lenb=B.size();
            vector<vector<int>> dp(lena+1,vector<int>(lenb+1,0));
            for(int i = 1; i <= lena; i++)
            {
        
                for (int j = 1; j <= lenb; j++) {
        
                    /* code */
                   if(A[i-1]==B[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[lena][lenb];
        }
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，4人围观）

还没有评论，来说两句吧...

相关阅读

相关 lintcode77. 最长公共子序列

给出两个字符串，找到最长公共子序列(LCS)，返回LCS的长度。样例样例 1: 输入: "ABCD" and "EDCA" 输出:

小灰灰/ 2023年07月03日 15:28/ 0 赞/ 5 阅读

相关最长公共子序列

最长公共子序列 1、参考资料 https://leetcode-cn.com/problems/longest-common-subsequence/ 2、题目

阳光穿透心脏的1/2处/ 2022年12月09日 04:57/ 0 赞/ 241 阅读

相关最长公共子序列

include <iostream> include <assert.h> include <string> using namesp

男娘i/ 2022年09月30日 10:00/ 0 赞/ 216 阅读

相关最长公共子序列

最长公共子序列时间限制：3000 ms | 内存限制：65535 KB 难度：3 描述咱们就不拐弯抹角了，如题，需要你做的就是写一个程序，得出最长公共子序列

骑猪看日落/ 2022年09月30日 06:28/ 0 赞/ 219 阅读

相关最长公共子序列空间优化最长公共子序列

import java.util.Scanner; / HDU 1159 @author ashzheng 201

ゞ浴缸里的玫瑰/ 2022年08月21日 05:46/ 0 赞/ 286 阅读

相关最长公共子序列

一个序列的子序列是该序列中删除某些元素后得到的序列。给定两个子序列X和Y，求二者的最长公共子序列。例如，X=\{A,B,C,B,D,A,B\}，Y=\{B,D,C,A,B,

超、凢脫俗/ 2022年08月02日 06:53/ 0 赞/ 214 阅读

相关最长公共子序列

最长公共子序列最长公共子序列与最长公共子串的区别在于最长公共子序列不要求在原字符串中是连续的，比如ADE和ABCDE的最长公共子序列是ADE。我们用动态规划的方法来思考

向右看齐/ 2022年06月03日 05:17/ 0 赞/ 217 阅读

相关最长公共子序列

最长公共子序列问题，具有最优子结构性质设序列Xm=\{x1,x2,…,xm\}和Yn=\{y1,y2,…,yn\}的最长公共子序列为Zk=\{z1

港控/mmm°/ 2022年04月23日 07:04/ 0 赞/ 273 阅读

相关最长公共子序列

找出两个字符串的最长公共子序列。 ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLm

r囧r小猫/ 2021年11月09日 17:10/ 0 赞/ 409 阅读

相关最长公共子序列

最长公共子序列设X=<x1,x2,x3,x4…,xm>，Y=<y1,y2,y3,y4…,yn>为两个序列，Z=<z1,z2,z3,z4…,zk>是他们的任意公共子序列

迈不过友情╰/ 2021年10月19日 05:48/ 0 赞/ 383 阅读