string - 如何在“edit_distance_problem”中重建字符串？

Question

假设您为字符串 X = "AGGGCT" 和字符串 Y = "AGGCA" 提供了 dp 表

m = X + 1 的长度

n = Y + 1 的长度

            0 1 2 3 4 5
            1 0 1 2 3 4
            2 1 0 1 2 3
dp[m][n] =  3 2 1 0 1 2
            4 3 2 1 1 2
            5 4 3 2 1 2
            6 5 4 3 2 2

你想重建三个字符串如下

string row1 = "AGGGCT" ;
string row2 = "||| | " ;
string row3 = "AGG-CA" ;

如果可能的话，如何用 C/C++/Java 重新构造字符串 row1、row2 和 row3。

Answer 1

我认为这个页面可以是一个很好的起点：

http://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Levenshtein_distance#Java

您必须进行一些修改，但核心思想应该是存储在“min”中，为给定的 (i,j) 选择了哪种情况，并且在返回之前，您可以从距离开始向后遍历矩阵 [str1 .length()][str2.length()] 一步一步。如果步骤中的距离相同，则显示 |，如果它们不同但跨步对角线，则这是一个更改步骤，否则如果垂直/水平则删除/添加。您可以将此“向后”信息存储在一个字符串中，然后以相反的顺序显示它。