Javascript最长公共子序列

问题描述 投票:0回答:2

我有一个必须返回结果的算法,如下所示:

/*
"ABAZDC", "BACBAD" => ABAD
"AGGTAB", "GXTXAYB" => GTAB
"aaaa", "aa" => "aa"
"", "..." => ""
"ABBA", "ABCABA" => "ABBA"
*/

我开发的代码没有返回这些结果。我该如何解决?

console.log(solution('ABAZDC', 'BACBAD')) 

function solution(str1, str2) {
  str1 = str1.split('')
  str2 = str2.split('')  

  const output = []

  for(let i = str1.length -1; i >= 0; i--) {   
    for(let j = str2.length -1; j >= 0; j--) {
      if( str2[j] === str1[i] ) {
        output.push(str2[j]) 
        break
      }      
    } 

  }

  return output.reverse().join('')

}

NOTE:

这里是youtube上的解决方案。但是,对我来说,这种解决方案非常复杂。我想得到一个更简单的解决方案,其中不包含递归方法或备注,以便像迭代解决方案一样更清楚地理解。

https://www.youtube.com/watch?v=10WnvBk9sZc&feature=youtu.be

javascript algorithm loops
2个回答
0
投票

关于如何在两个字符串之间找到LCS的很好解释可以在https://alfedenzo.livejournal.com/170301.html中找到。我在我的PatienceDiff的javascript解决方案中使用了该文章,该文章位于https://github.com/jonTrent/PatienceDiff


-1
投票

您只需要添加一个检查,确定是否已经添加了与该字符匹配的字符,例如! output.contains(str2[j] )或以下

    function solution(str1, str2) {
  str1 = str1.split('')
  str2 = str2.split('')  

  const output = []

  for(let i = str1.length -1; i >= 0; i--) {   
    for(let j = str2.length -1; j >= 0; j--) {
      if( str2[j] === str1[i]
          ) {
          str2.replace(str2[j], "" ) ;
        output.push(str2[j]) 
        break
      }      
    } 

  }
© www.soinside.com 2019 - 2024. All rights reserved.