首页 > 试题广场 >

最长公共子序列(二)

[编程题]最长公共子序列(二)

热度指数：140122 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定两个字符串str1和str2，输出两个字符串的最长公共子序列。如果最长公共子序列为空，则返回"-1"。目前给出的数据，仅仅会存在一个最长的公共子序列

数据范围： $0 \le |str1|,|str2| \le 2000$

要求：空间复杂度 $O(n^2)$ ，时间复杂度 $O(n^2)$

示例1

输入

"1A2C3D4B56","B1D23A456A"

输出

"123456"

示例2

输入

"abc","def"

输出

"-1"

示例3

输入

"abc","abc"

输出

"abc"

示例4

输入

"ab",""

输出

"-1"

算法知识视频讲解

Javascript

牛客853217693号

JavaScript版本

严格表结构：

/**
 * longest common subsequence
 * @param s1 string字符串 the string
 * @param s2 string字符串 the string
 * @return string字符串
 */
function LCS(s1, s2) {
    if (!s1 || !s2 || s1.length < 1 || s2.length < 1) return -1;
    // write code here
    // 严格表结构
    return process2(s1, s2) === "" ? -1 : process2(s1, s2);
}

// 严格表结构
function process2(s1, s2) {
    let row = s1.length;
    let col = s2.length;
    let dp = [...Array(row)].map((v) => (v = [...Array(col)].fill(0)));
    dp[0][0] = s1[0] == s2[0] ? s1[0] : "";
    for (let i = 1; i < row; i++) {i
        dp[i][0] = s1[i] == s2[0] ? s1[i] : dp[i-1][0];
    }
    for (let i = 1; i < col; i++) {
        dp[0][i] = s1[0] == s2[i] ? s2[i] : dp[0][i-1];
    }
    for (let i = 1; i < row; i++) {
        for (let j = 1; j < col; j++) {
            let p1 = s1[i] === s2[j] ? dp[i - 1][j - 1] + s1[i] : "";
            let p2 = dp[i - 1][j];
            let p3 = dp[i][j - 1];
            let h = p1.length > p2.length ? p1 : p2;
            dp[i][j] = h.length > p3.length ? h : p3;
        }
    }
    return dp[row - 1][col - 1];
}

module.exports = {
    LCS: LCS,
};

记忆化搜索：

/**
 * longest common subsequence
 * @param s1 string字符串 the string
 * @param s2 string字符串 the string
 * @return string字符串
 */
function LCS(s1, s2) {
    if (!s1 || !s2 || s1.length < 1 || s2.length < 1) return -1;
    // write code here
    // 记忆化搜索
    // let dp = [...Array(s1.length + 1)].map(
    //     (v) => (v = [...Array(s2.length + 1)].fill(-2))
    // );
    // return process1(s1, s2, s1.length - 1, s2.length - 1, dp) === ""
    //     ? -1
    //     : process1(s1, s2, s1.length - 1, s2.length - 1, dp);
}

// 记忆化搜索
function process1(s1, s2, i, j, dp) {
    if (dp[i][j] !== -2) return dp[i][j];
    if (i === 0 && j === 0) {
        dp[i][j] = s1[i] === s2[j] ? s1[i] : "";
    } else if (i === 0 && j !== 0) {
        dp[i][j] = s1[i] === s2[j] ? s1[i] : process1(s1, s2, i, j - 1, dp);
    } else if (j === 0 && i !== 0) {
        dp[i][j] = s1[i] === s2[j] ? s1[i] : process1(s1, s2, i - 1, j, dp);
    } else {
        // i!=0 && j!=0
        // 相等
        let p1 =
            s1[i] === s2[j] ? process1(s1, s2, i - 1, j - 1, dp) + s1[i] : "";
        //不相等：1. i-- 2.j--
        let p2 = process1(s1, s2, i - 1, j, dp);
        let p3 = process1(s1, s2, i, j - 1, dp);
        let h = p1.length > p2.length ? p1 : p2;
        dp[i][j] = h.length > p3.length ? h : p3;
    }
    return dp[i][j];
}
module.exports = {
    LCS: LCS,
};

暴力递归：超时

/**
 * longest common subsequence
 * @param s1 string字符串 the string
 * @param s2 string字符串 the string
 * @return string字符串
 */
function LCS(s1, s2) {
    if (!s1 || !s2 || s1.length < 1 || s2.length < 1) return -1;
    // write code here
     return process(s1, s2, s1.length - 1, s2.length - 1) === ""
         ? -1
         : process(s1, s2, s1.length - 1, s2.length - 1);
}

// 暴力递归 O(n^2)运行超时
function process(s1, s2, i, j) {
    if (i === 0 && j === 0) return s1[i] === s2[j] ? s1[i] : "";
    if (i === 0 && j !== 0) {
        return s1[i] === s2[j] ? s1[i] : process(s1, s2, i, j - 1);
    }
    if (j === 0 && i !== 0) {
        return s1[i] === s2[j] ? s1[i] : process(s1, s2, i - 1, j);
    }
    // i!=0 && j!=0
    // 相等
    let p1 = s1[i] === s2[j] ? process(s1, s2, i - 1, j - 1) + s1[i] : "";
    //不相等：1. i-- 2.j--
    let p2 = process(s1, s2, i - 1, j);
    let p3 = process(s1, s2, i, j - 1);
    let h = p1.length > p2.length ? p1 : p2;
    return h.length > p3.length ? h : p3;
    // return Math.max(p1, Math.max(p3, p2));
}
module.exports = {
    LCS: LCS,
};

发表于 2023-02-19 19:34:02 回复(0)

Javascript

越过森林越过风

JS 思路：

1、 dp[i][j]表示长度为[0,i-1]的字符串text1,和长度为[0,j-1]的字符串text2的最长公共子序列为dp[i][j]，此处表示串

2、递推公式，text1[i-1]和text2[j-1]是否相等/不相同，相同就是一个公共元素，dp[i][j]=dp[i-1][j-1]+text1[i-1]；不相同，就需要看text1[0,i-2]和text2[0,j-1]的最长公共子序列，和text1[0,i-1]和text2[0,j-2]的最长公共子序列，取长度最大的串
3、初始化，dp[i][0]='',dp[0][j]=''
4、遍历顺序，上到下，左到右
5、举例推导说明

function LCS( s1 ,  s2 ) {
    let m=s1.length,n=s2.length
    let dp=Array.from(Array(m+1),()=>Array(n+1).fill(''))
    for(let i=1;i<=m;i++){
        for(let j=1;j<=n;j++){
            if(s1[i-1]==s2[j-1]){
                dp[i][j]=dp[i-1][j-1]+s1[i-1]
            }else{
                dp[i][j]=(dp[i-1][j]).length>(dp[i][j-1]).length?dp[i-1][j]:dp[i][j-1]
            }
        }
    }
    return dp[m][n]==''?-1:dp[m][n]
}

发表于 2022-08-17 08:06:00 回复(0)

Javascript

小舟不系

function LCS( text1 ,  text2 ) {
  let dp = new Array(text1.length + 1).fill('').map(() => new Array(text2.length + 1).fill(''));
  for (let i = 1; i <= text1.length; i++) {
    for (let j = 1; j <= text2.length; j++) {
      if (text1[i - 1] === text2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + '' + text1[i-1];
      } else {
        dp[i][j] = dp[i-1][j].length>dp[i][j-1].length ? dp[i-1][j] : dp[i][j-1];
      }
    }
  }
  return dp[text1.length][text2.length]===''? -1 : dp[text1.length][text2.length];
}
module.exports = {
    LCS : LCS
};

发表于 2022-08-10 00:31:12 回复(0)

Javascript

牛客343123665号

function LCS( s1 ,  s2 ) {
    // write code here
 if (s1.length === 0 || s2.length === 0) return -1;
 let dp = Array(s1.length +1).fill(0).map(() => Array((s2.length + 1)).fill(0));

 for(let i=1;i<=s1.length;i++) {
     for(let j=1;j<=s2.length;j++) {
         if (s1[i-1] === s2[j-1]) {
             dp[i][j] = dp[i-1][j-1] + 1;
         } else {
             dp[i][j] = Math.max(dp[i][j-1], dp[i-1][j]);
         }
     }
 }
 
 let strArr = [];
 for(let i=s1.length,j=s2.length; i>=0 && j >=0 && dp[i][j]>0; ) {
     if (s1[i-1] === s2[j-1]) {
         strArr.push(s1[i-1]);
         i--;
         j--
     } else if (i == 0 || dp[i][j-1]> dp[i-1][j]) {
         j--
     } else {
         i--
     }
 }
 if (strArr.length === 0) return -1;
 return strArr.reverse().join('');
}

发表于 2022-07-29 16:36:17 回复(0)

JavaScript

splwany

js测试用例是错的，正确代码应该这样：

function LCS( s1 ,  s2 ) {
    if (s1.length > s2.length) [s1, s2] = [s2, s1];
    const dp = new Array(s2.length + 1).fill('');
    for (let i = 1; i <= s1.length; i++) {
        let pre = '';
        for (let j = 1; j <= s2.length; j++) {
            const tmp = dp[j];
            if (s1[i - 1] === s2[j - 1]) dp[j] = pre + s2[j - 1];
            else dp[j] = dp[j].length > dp[j - 1].length ? dp[j] : dp[j - 1];
            pre = tmp;
        }
    }
    const res = dp[s2.length];
    return res === '' ? '-1' : res;
}

编辑于 2021-04-07 15:59:15 回复(0)

JavaScript

别卷啦！

遇到这种最长序列子串数组一般都是动态规划做个二维数组

function LCS( s1 ,  s2 ) {
    // write code here
    let m = s1.length, n = s2.length
    let dp = Array.from(new Array(m+1),() => new Array(n+1).fill('')) //做个二维矩阵
    for(let i = 1;i<=m;i++){
        for(let j = 1;j<=n;j++){
            if(s1[i-1] == s2[j-1]){
               dp[i][j] = dp[i-1][j-1] + s1[i-1] //对角线
            }else{
                dp[i][j] = dp[i-1][j].length > dp[i][j-1].length ? dp[i-1][j] : dp[i][j-1]  
            }
        }
    }
    return dp[m][n] == '' ? -1 : dp[m][n] 
}

发表于 2021-01-18 21:42:34 回复(0)

JavaScript

Neptune_JNQ

js动态规划

function LCS( s1 ,  s2 ) {
    if(!s1 || !s2) return -1;
    
    let m = s1.length, n = s2.length;
    let dp = Array.from(new Array(m+1), ()=>new Array(n+1).fill(''));
    for(let i=1; i<m+1; i++){
        for(let j=1; j<n+1; j++){
            if(s1[i-1] == s2[j-1]) dp[i][j] = dp[i-1][j-1]+s1[i-1];
            else dp[i][j] = dp[i-1][j].length > dp[i][j-1].length ? dp[i-1][j]:dp[i][j-1];            
        }
    }
    return dp[m][n] == ''?-1:dp[m][n];
}

发表于 2020-12-08 12:14:17 回复(0)

提交观点

问题信息

动态规划

难度：

7条回答 2254收藏 12485浏览

通过挑战的用户

查看代码

freeemann

2023-02-21 14:40:59
UchihaM...

2023-01-05 22:57:07
牛客95991...

2023-01-05 10:24:08
希望被offe...

2022-11-11 00:24:25
无所畏惧201...

2022-11-10 22:31:05

最长公共子序列(二)

输入

输出

输入

输出

输入

输出

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题