英文:
Go : longest common subsequence back tracing
问题
我的代码可以计算最长公共子序列（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)
}
}
}
提前感谢你的帮助。
英文:
My code works for Computing the length of the LCS but I apply the same code for Reading out an LCS on the following link,
http://en.wikipedia.org/wiki/Longest_common_subsequence_problem
but some strings are missing. Could you tell me what I am missing?
Google Playground link : 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)
}
}
}
Thanks in advance.
答案1
得分: 2
我认为问题出在你的索引上。如果你将字符串从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。
英文:
The problem I think is in your indexing. If you are indexing your strings from 0-len-1, your table should have number of rows and cols, 1 greater than length of strings. It seems that you have accounted that when calculating the length of LCS, but not when you are returning a LCS. Your i and j correctly represent the index for strings, but not for table, which should be 1 greater than i/j. So your base condition of checking for 0 is wrong as str1[0] and str2[0] are valid characters
So your code should look like:
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)
}
}
}
Here is Live Code
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论