剑指offer 最长公共子序列

小鱼儿 2022-06-09 11:24 30阅读 0赞

# 1.题目 #

我们有两个字符串m和n，如果它们的子串a和b内容相同，则称a和b是m和n的公共子序列。子串中的字符不一定在原字符串中连续。  
例如字符串“abcfbc”和“abfcab”，其中“abc”同时出现在两个字符串中，因此“abc”是它们的公共子序列。此外，“ab”、“af”等都是它们的字串。  
现在给你两个任意字符串（不包含空格），请帮忙计算它们的最长公共子序列的长度。

注意：子序列≠子串，子序列不是连续的，保持原有相对顺序即可。

# 2. 分析 #

动态规划。  
dp\[i\]\[j\]表示str1\[0..i\]和str2\[0..j\]  
建立一个dp矩阵，是两个字符串一个纵对应，一个横向对应。  
dp\[i\]\[j\]表示str1\[0…i\]和str2\[0…j\]的最长公共子序列的长度

若str1\[i\] == str2\[j\]，则 dp\[i\]\[j\] = dp\[i-1\]\[j-1\]+1  
若str1\[i\] != str2\[j\]，则 dp\[i\]\[j\] = max( dp\[i-1\]\[j\], dp\[i\]\[j-1\] )

# 3.代码 #

class LCS {
    public:
        int findLCS(string A, int n, string B, int m) {
            int dp[n+1][m+1];
            for(int i=0;i<=n;i++)
                dp[i][0]=0;
            for(int j=0;j<=m;j++)
                dp[0][j]=0;
            for(int i=0;i<n;i++)
            {
                for(int j=0;j<m;j++){
                    if(A[i]==B[j])
                        dp[i+1][j+1]=dp[i][j]+1;
                    else
                        dp[i+1][j+1]=max(dp[i+1][j],dp[i][j+1]);
                }    
            }
            return dp[n][m];
        }
    };

发表评论取消回复

表情：

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

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

相关阅读

相关最长公共子序列

最长公共子序列 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 赞/ 215 阅读

相关剑指offer 最长公共子序列

1.题目我们有两个字符串m和n，如果它们的子串a和b内容相同，则称a和b是m和n的公共子序列。子串中的字符不一定在原字符串中连续。例如字符串“abcfbc”和“a

小鱼儿/ 2022年06月09日 11:24/ 0 赞/ 31 阅读

相关最长公共子序列

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

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

相关最长公共子序列

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

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

相关最长公共子序列

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

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

相关最长公共子序列

最长公共子序列设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 阅读