Edit Distance问题

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

int minDistanceRecursion(string & word1, string & word2, int i, int j)
{
    if (j == 0)
    {
        return i;
    }
    else if (i == 0)
    {
        return j;
        
    }
    else if (word1[i - 1] == word2[j - 1])
    {
        return minDistanceRecursion(word1, word2, i - 1, j - 1);
    }
    else
    {

        return min_of_three(minDistanceRecursion(word1, word2, i - 1, j) + 1,
                            minDistanceRecursion(word1, word2, i, j - 1) + 1,
                            minDistanceRecursion(word1, word2, i - 1, j - 1) + 1);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

int min_of_three(int a, int b, int c)
{
    return min(a, min(b, c));
}

int minDistanceDp(string word1, string word2)
{
    int m = word1.length();
    int n = word2.length();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1));

    // 初始化空字符串的情况
    for (int i = 1; i <= m; ++i)
    {
        dp[i][0] = i;
    }

    for (int i = 1; i <= n; ++i)
    {
        dp[0][i] = i;
    }

    for (int i = 1; i <= m; ++i)
    {
        for (int j = 1; j <= n; ++j)
        {
            // 增加操作：str1a变成str2后再加上b，得到str2b
            int insertion = dp[i][j - 1] + 1;

            // 删除操作：str1a删除a后，再由str1变为str2b
            int deletion = dp[i - 1][j] + 1;

            // 替换操作：先由str1变为str2，然后str1a的a替换为b，得到str2b
            //int replace = dp[i - 1][j - 1] + (word1[i - 1] == word2[j - 1] ? 0 : 1);
            int replace = 0;
            if (word1[i - 1] == word2[j - 1])
            {
                replace = 0;
            }
            else
            {
                replace = 1;
            }
            replace += dp[i - 1][j - 1];

            // 三者取最小
            //dp[i][j] = min(replace, min(insertion, deletion));
            dp[i][j] = min_of_three(replace,insertion,deletion);
        }
    }
    return dp[m][n];
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

int main()
{
    string source = "AGTCTGACGC";
    string target = "AGTAAGTAGGC";
    cout << source << "->" << target << '\n';
    cout << "edit distance Dp = " << minDistanceDp(source, target) << '\n';
    cout << "edit distance Recursion = ";
    cout << minDistanceRecursion(source, target, source.length(), target.length()) << '\n';

    return 0;
}