我有一个必须返回结果的算法,如下所示:
/*
"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
关于如何在两个字符串之间找到LCS的很好解释可以在https://alfedenzo.livejournal.com/170301.html中找到。我在我的PatienceDiff的javascript解决方案中使用了该文章,该文章位于https://github.com/jonTrent/PatienceDiff。
您只需要添加一个检查,确定是否已经添加了与该字符匹配的字符,例如! 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
}
}
}