算法或者代码算法Leetcode

算法学习——DP（二）

2017-09-05  本文已影响33人  徐涌盛

LCS问题（最长公共子序列）

上一篇文章
所有代码和markdown在chux0519/algs同步更新。

计算LCS长度

递归解法

LCS问题是具有最优子结构的。
假设长度为m的字符串X[0..m-1]和长度为n的字符串Y[0..n-1]，用L(X[0..m-1], Y[0..n-1]) 来表示它们的LCS长度。则可以得到以下结论：

  1. 如果X[m-1] = Y[n-1], 那么L(X[0..m-1], Y[0..n-1]) = 1 + L(X[0..m-2], Y[0..n-2])
  2. 如果X[m-1] != Y[n-1], 那么L(X[0..m-1], Y[0..n-1]) = MAX ( L(X[0..m-2], Y[0..n-1]), L(X[0..m-1], Y[0..n-2])

用JS描述如下

function lcs (str1, str2, len1, len2) {
  if (len1 === 0 || len2 === 0) return 0
  if (str1[len1] === str2[len2]) {
    return 1 + lcs(str1, str2, len1 - 1, len2 - 1)
  } else {
    return Math.max(
      lcs(str1, str2, len1 - 1, len2),
      lcs(str1, str2, len1, len2 - 1)
    )
  }
}

进一步分析

假设X="AXYT", Y="AYZX"，画出以上代码的调用图，得到：

                         lcs("AXYT", "AYZX")
                       /                 
         lcs("AXY", "AYZX")            lcs("AXYT", "AYZ")
         /                              /               
lcs("AX", "AYZX") lcs("AXY", "AYZ")   lcs("AXY", "AYZ") lcs("AXYT", "AY")

可以看出lcs("AXY", "AYZ")被重复计算了，随着层数的增多，可以分析出，有许多重复子问题会出现，于是，可以利用记忆化或者制表来进行优化算法。

制表解法

// tab
function lcsWithTab (str1, str2, len1, len2) {
  var tab = new Array(len1 + 1).fill([])
  for (var i = 0; i <= len1; i++) {
    for (var j = 0; j <= len2; j++) {
      if (i === 0 || j === 0) {
        tab[i][j] = 0
      } else if (str1[i - 1] === str2[j - 1]) {
        tab[i][j] = tab[i - 1][j - 1] + 1
      } else {
        tab[i][j] = Math.max(
          tab[i - 1][j],
          tab[i][j - 1]
        )
      }
    }
  }
  return tab[len1][len2]
}

制表解法，通过定义好基线条件tab[i][j] = 0 where i ==0 || j == 0，自底向上计算出结果，提升速度的同时消除了递归。

回溯LCS

存储回溯数组

在上述算法中，增加一个数组用于存储回溯路径即可，稍作改动如下。

function LCS (str1, str2, len1, len2) {
  var tab = []
  var back = []
  for (var m = 0; m <= len1; m++) {
    tab[m] = []
    back[m] = []
    for (var n = 0; n <= len2; n++) {
      tab[m][n] = null
      back[m][n] = null
    }
  }

  for (var i = 0; i <= len1; i++) {
    for (var j = 0; j <= len2; j++) {
      if (i === 0 || j === 0) {
        tab[i][j] = 0
        back[i][j] = null
      } else if (str1[i - 1] === str2[j - 1]) {
        tab[i][j] = tab[i - 1][j - 1] + 1
        back[i][j] = '↖'
      } else if (tab[i - 1][j] > tab[i][j - 1]) {
        tab[i][j] = tab[i - 1][j]
        back[i][j] = '↑'
      } else if (tab[i - 1][j] === tab[i][j - 1]) {
        tab[i][j] = tab[i - 1][j]
        back[i][j] = '←/↑'
      } else {
        tab[i][j] = tab[i][j - 1]
        back[i][j] = '←'
      }
    }
  }
  return { tab: tab, bt: back }
}

运行

var str1 = 'GAC'
var str2 = 'AGCAT'
var result = LCS(str1, str2, str1.length, str2.length)
console.log(result.tab)
console.log(result.bt)

可以得到如下输出：

[ [ 0, 0, 0, 0, 0, 0 ],
  [ 0, 0, 1, 1, 1, 1 ],
  [ 0, 1, 1, 1, 2, 2 ],
  [ 0, 1, 1, 2, 2, 2 ] ]
[ [ null, null, null, null, null, null ],
  [ null, '←/↑', '↖', '←', '←', '←' ],
  [ null, '↖', '←/↑', '←/↑', '↖', '←' ],
  [ null, '↑', '←/↑', '↖', '←/↑', '←/↑' ] ]

tab数组的输出为LCS的长度，�bt数组的内容是回溯的方向，例子取自维基百科。

输出一个LCS

输出LCS结果，需要利用bt数组进行回溯，只输出一个LCS时，可以用以下回溯函数。

function backtrace (bt, str1, str2, i, j) {
  if (i === 0 || j === 0) {
    return ''
  } else if (bt[i][j] === '↖') {
    return backtrace(bt, str1, str2, i - 1, j - 1) + str1[i]
  } else {
    if (bt[i][j] === '←') {
      return backtrace(bt, str1, str2, i, j - 1)
    } else {
      return backtrace(bt, str1, str2, i - 1, j)
    }
  }
}
console.log(backtrace(result.bt, str1, str2, str1.length, str2.length))

得到输出AC

实际上不用bt数组，直接使用保存LCS长度的tab数组也能直接回溯。稍微修改backtrace的判断条件即可。如下：

function backtraceByTab (tab, str1, str2, i, j) {
  if (i === 0 || j === 0) {
    return ''
  } else if (str1[i - 1] === str2[j - 1]) {
    return backtraceByTab(tab, str1, str2, i - 1, j - 1) + str1[i]
  } else {
    if (tab[i][j - 1] > tab[i - 1][j]) {
      return backtraceByTab(tab, str1, str2, i, j - 1)
    } else {
      return backtraceByTab(tab, str1, str2, i - 1, j)
    }
  }
}
console.log(backtraceByTab(result.tab, str1, str2, str1.length, str2.length))

得到输出仍旧为AC

20170906 update

输出所有LCS

输出所有LCS结果，在这里使用保存LCS长度的tab数组。
wiki给出的伪代码如下

function backtrackAll(C[0..m,0..n], X[1..m], Y[1..n], i, j)
    if i = 0 or j = 0
        return {""}
    else if X[i] = Y[j]
        return {Z + X[i] for all Z in backtrackAll(C, X, Y, i-1, j-1)}
    else
        R := {}
        if C[i,j-1] ≥ C[i-1,j]
            R := R ∪ backtrackAll(C, X, Y, i, j-1)
        if C[i-1,j] ≥ C[i,j-1]
            R := R ∪ backtrackAll(C, X, Y, i-1, j)
        return R

使用JS实现如下

// backtrace all
function backtraceAllByTab (tab, str1, str2, i, j) {
  function _backtraceAllByTab (tab, str1, str2, i, j) {
    if (i === 0 || j === 0) {
      return ['']
    } else if (str1[i - 1] === str2[j - 1]) {
      return [].map.call(_backtraceAllByTab(tab, str1, str2, i - 1, j - 1), each => each + str1[i - 1])
    } else {
      var r = []
      if (tab[i][j - 1] >= tab[i - 1][j]) {
        r = r.concat(_backtraceAllByTab(tab, str1, str2, i, j - 1)) // 本应该求并集，这里直接连接起来，最后去重一次
      }
      if (tab[i - 1][j] >= tab[i][j - 1]) {
        r = r.concat(_backtraceAllByTab(tab, str1, str2, i - 1, j)) // 本应该求并集，这里直接连接起来，最后去重一次
      }
      return r
    }
  }
  return Array.from(new Set(_backtraceAllByTab(tab, str1, str2, i, j))) // 去重
}

调用

var str1 = 'GAC'
var str2 = 'AGCAT'
console.log(backtraceAllByTab(result.tab, str1, str2, str1.length, str2.length))

输出

[ 'AC', 'GC', 'GA' ]

值得注意的是，输出所有的LCS是不保证时间复杂度为多项式复杂度的，如果两个字符串比较接近，那么可能每一步都会有分枝。

输出diff

这里JS实现完全参考wiki，等号的判定条件放在>=中，若将其替换为'>'，则diff的输出可能不同。

function printDiff (tab, str1, str2, i, j) {
  if (i > 0 && j > 0 && str1[i - 1] === str2[j - 1]) {
    printDiff(tab, str1, str2, i - 1, j - 1)
    console.log(`  ${str1[i - 1]}`)
  } else if (j > 0 && tab[i][j - 1] >= tab[i - 1][j]) {
    printDiff(tab, str1, str2, i, j - 1)
    console.log(`+ ${str2[j - 1]}`)
  } else if (i > 0) {
    printDiff(tab, str1, str2, i - 1, j)
    console.log(`- ${str1[i - 1]}`)
  } else {
    console.log('')
  }
}

调用

var str1 = 'GAC'
var str2 = 'AGCAT'
printDiff(result.tab, str1, str2, str1.length, str2.length)

输出

- G
  A
+ G
  C
+ A
+ T

思考——算法优化

上一篇下一篇

猜你喜欢

热点阅读