算法：动态规划求最长公共子序列(LCS)

2019-04-14 1420次浏览

找出两个串中最长公共子序列：

function lcs (sText1, sText2) {
  let l1 = sText1.length, l2 = sText2.length
  let l = []
  for (let i = 0; i < l1 + 1; i++) l.push(new Array(l2 + 1).fill(0))
  for (let i = 0; i < l1; i++) {
    for (let j = 0; j < l2; j++) {
      if (sText1[i] === sText2[j]) {
        l[i+1][j+1] = l[i][j] + 1
      } else {
        l[i+1][j+1] = Math.max(l[i][j+1], l[i+1][j])
      }
    }
  }
  return l
}

function lcs_solution (sText1, sText2) {
  let l = lcs(sText1, sText2)
  let i = sText1.length, j = sText2.length
  let list = []
  while (l[i][j] > 0) {
    if (sText1[i-1] === sText2[j-1]) {
      list.push(sText1[i-1])
      i--
      j--
    } else if (l[i-1][j] >= l[i][j-1]) {
      i--
    } else {
      j--
    }
  }
  return list.reverse()
}

console.log(lcs_solution('abcdefghij', 'abdadsegfg'))
¥赞赏