0

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

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

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

谷歌游乐场链接： 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)
    }
  }
}

提前致谢。

4

1 回答 1

2

我认为问题在于您的索引。如果你从0-索引你的字符串len-1，你的表应该有行数和列数，比字符串的长度大 1。似乎您在计算 LCS 的长度时已经考虑到了这一点，但在返回 LCS 时却没有。您的i和j正确表示字符串的索引，但不是表的索引，它应该大于 1 i/j。因此，您检查 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)
    }
  }
}

这是实时代码

于 2013-11-22T23:42:52.317 回答