algorithm - 转到 : longest common subsequence back tracing

Question

我的代码适用于计算 LCS 的长度，但我在以下链接中应用相同的代码来读取 LCS，

http://en.wikipedia.org/wiki/Longest_common_subsequence_problem

但缺少一些字符串。你能告诉我我错过了什么吗？

Google Playground 链接:http://play.golang.org/p/qnIWQqzAf5

func Back(table [][]int, str1, str2 string, i, j int) string {
  if i == 0 || j == 0 {
    return ""
  } else if str1[i] == str2[j] {
    return Back(table, str1, str2, i-1, j-1) + string(str1[i])
  } else {
    if table[i][j-1] > table[i-1][j] {
      return Back(table, str1, str2, i, j-1)
    } else {
      return Back(table, str1, str2, i-1, j)
    }
  }
}

提前致谢。

Answer 1

我认为问题在于您的索引。如果您从 0-len-1 索引您的字符串，您的表应该有行数和列数，比字符串长度大 1。看来您在计算 LCS 的长度时已经考虑到了这一点，但在返回 LCS 时却没有考虑到这一点。您的 i 和 j 正确表示字符串的索引，但不是表的索引，它应该比 i/j 大 1。因此，您检查 0 的基本条件是错误的，因为 str1[0] 和 str2[0] 是有效字符

所以你的代码应该是这样的:

func Back(table [][]int, str1, str2 string, i, j int) string {
  if i == -1 || j == -1 {
    return ""
  } else if str1[i] == str2[j] {
    return Back(table, str1, str2, i-1, j-1) + string(str1[i])
  } else {
    if table[i+1][j] > table[i][j+1] {
      return Back(table, str1, str2, i, j-1)
    } else {
      return Back(table, str1, str2, i-1, j)
    }
  }
}

这里是 Live Code