javascript实现最长公共子序列实例代码(6)

日期：2020-05-11 栏目：程序人生浏览：次

打印一个LCS

我们再给出打印函数，先看如何打印一个。我们从右下角开始寻找，一直找到最上一行终止。因此目标字符串的构建是倒序。为了避免使用stringBuffer这样麻烦的中间量，我们可以通过递归实现，每次执行程序时，只返回一个字符串，没有则返回一个空字符串，以 printLCS(x,y,...) + str[i] 相加，就可以得到我们要求的字符串。

我们再写出一个方法，来验证我们得到的字符串是否真正的LCS字符串。作为一个已经工作的人，不能写的代码像在校生那样，不做单元测试就放到线上让别人踩坑。

//by 司徒正美，打印一个LCS
function printLCS(dp, str1, str2, i, j){
 if (i == 0 || j == 0){
  return "";
 }
 if( str1[i-1] == str2[j-1] ){
  return printLCS(dp, str1, str2, i-1, j-1) + str1[i-1];
 }else{
  if (dp[i][j-1] > dp[i-1][j]){
   return printLCS(dp, str1, str2, i, j-1);
  }else{
   return printLCS(dp, str1, str2, i-1, j);
  }
 }
}
//by司徒正美， 将目标字符串转换成正则，验证是否为之前两个字符串的LCS
function validateLCS(el, str1, str2){
 var re = new RegExp( el.split("").join(".*") )
 console.log(el, re.test(str1),re.test(str2))
 return re.test(str1) && re.test(str2)
}

使用：

function LCS(str1, str2){
 var m = str1.length 
 var n = str2.length
 //....略，自行补充
 var s = printLCS(dp, str1, str2, m, n)
 validateLCS(s, str1, str2)
 return dp[m][n]
}
var c1 = LCS( "ABCBDAB","BDCABA");
console.log(c1) //4 BCBA、BCAB、BDAB
var c2 = LCS("13456778" , "357486782" );
console.log(c2) //5 34678 
var c3 = LCS("ACCGGTCGAGTGCGCGGAAGCCGGCCGAA" ,"GTCGTTCGGAATGCCGTTGCTCTGTAAA" );
console.log(c3) //20 GTCGTCGGAAGCCGGCCGAA

打印全部LCS

思路与上面差不多，我们注意一下，在LCS方法有一个Math.max取值，这其实是整合了三种情况，因此可以分叉出三个字符串。我们的方法将返回一个es6集合对象，方便自动去掉。然后每次都用新的集合合并旧的集合的字任串。

//by 司徒正美 打印所有LCS
function printAllLCS(dp, str1, str2, i, j){
 if (i == 0 || j == 0){
  return new Set([""])
 }else if(str1[i-1] == str2[j-1]){
  var newSet = new Set()
  printAllLCS(dp, str1, str2, i-1, j-1).forEach(function(el){
   newSet.add(el + str1[i-1])
  })
  return newSet
 }else{
  var set = new Set()
  if (dp[i][j-1] >= dp[i-1][j]){
   printAllLCS(dp, str1, str2, i, j-1).forEach(function(el){
    set.add(el)
   })
  }
  if (dp[i-1][j] >= dp[i][j-1]){//必须用>=，不能简单一个else搞定
   printAllLCS(dp, str1, str2, i-1, j).forEach(function(el){
    set.add(el)
   })
  } 
  return set
 } 
 }

转载注明出处：http://www.heiqu.com/470.html

javascript实现最长公共子序列实例代码(6)

相关推荐