最长公共子序列（C++牛客网）

ゝ一纸荒年。 2022-11-17 10:15 196阅读 0赞

解题思路：

（1）动态规划

class Solution {
    public:
        /**
         * longest common subsequence
         * @param s1 string字符串 the string
         * @param s2 string字符串 the string
         * @return string字符串
         */
        string LCS(string str1, string str2) {
            int m=str1.length(),n=str2.length();
            vector<vector<int>> v(m+1,vector<int>(n+1,0));
            for(int i=0;i<m+1;i++) {
                for(int j=0;j<n+1;j++) {
                    if(i==0 || j==0) v[i][j]=0;
                    else if(str1[i-1]==str2[j-1]) v[i][j]=v[i-1][j-1]+1;
                    else v[i][j]=max(v[i-1][j],v[i][j-1]);
                }
            }
            
            string str="";
            int i=m,j=n;
            while(i>=1 && j>=1) {
                if(str1[i-1]==str2[j-1]) {
                    str=str1[i-1]+str;
                    i--;
                    j--;
                } else if(v[i-1][j]>v[i][j-1]) {
                    i--;
                } else j--;
            }
            if(str=="") return "-1";
            else return str;
        }
    };

发表评论取消回复

表情：

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

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

相关阅读

相关牛客最长公共子序列问题

题目链接：[https://www.nowcoder.com/practice/4727c06b9ee9446cab2e859b4bb86bb8?tpId=101&tqId=3

短命女/ 2023年06月04日 14:54/ 0 赞/ 66 阅读

相关牛客最长递增子序列

题目链接：[https://www.nowcoder.com/practice/30fb9b3cab9742ecae9acda1c75bf927?tpId=101&tqId=3

妖狐艹你老母/ 2023年06月04日 14:54/ 0 赞/ 17 阅读

相关最长公共前缀（C++牛客网）

解题思路：（1）先排序，再从长到短比较 class Solution { public: / @

亦凉/ 2022年11月18日 10:50/ 0 赞/ 199 阅读

相关最长递增子序列（C++牛客网）

include <vector> include <algorithm> using namespace std; class Sol

逃离我推掉我的手/ 2022年11月18日 02:25/ 0 赞/ 181 阅读

相关最长公共子序列（C++牛客网）

解题思路：（1）动态规划 class Solution { public: / longest common subs

ゝ一纸荒年。/ 2022年11月17日 10:15/ 0 赞/ 197 阅读

相关最长公共子串（C++牛客网）

解题思路：（1）动态规划 class Solution { public: / longest common subs

柔情只为你懂/ 2022年11月17日 05:22/ 0 赞/ 204 阅读

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

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

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

相关最长公共子序列

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

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

相关最长公共子序列

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

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

相关【牛客】回文串（最长公共子序列）

题目描述给定一个字符串，问是否能通过添加一个字母将其变为回文串。输入描述: 一行一个由小写字母构成的字符串，字符串长度小于等于10。输出描述:

雨点打透心脏的1/2处/ 2021年10月03日 02:32/ 0 赞/ 270 阅读