题目链接：Edit Distance

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)

You have the following 3 operations permitted on a word:

a) Insert a character 
b) Delete a character 
c) Replace a character

这道题的要求是计算两个单词的距离，即从word1转换到word2所需要的最少步数。可以有三种操作：插入字符、删除字符、替换字符。

计算单词间的距离，令d[i, j]表示word1的前i个字符与word2的前j个字符之间的距离。则d[i, j]的值有如下几种情况：

  1. 如果word1[i-1]等于word2[j-1]，则表明该位置不需要操作，即d[i, j] = d[i-1, j-1]；
  2. 如果word1[i-1]不等于word2[j-1]，则可能需要删除或添加或替换字符。如果需要删除或添加字符（删除和添加实为相反操作，这里只考虑删除吧）。可以选择删除word1[i-1]，这样d[i, j]就是word1的前i-1位和word2的前j位的距离再加1步删除操作，即d[i, j] = d[i-1, j] + 1。如果删除word1[j-1]，则d[i, j] = d[i, j-1] + 1。当然，如果替换，则d[i, j] = d[i-1, j-1] + 1。因此，d[i, j] = min(d[i-1, j], d[i, j-1], d[i-1, j-1]) + 1。

时间复杂度：O(mn)

空间复杂度：O(mn)

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

class Solution
{
public:
    int minDistance(string word1, string word2)
    {
        int l1 = word1.size(), l2 = word2.size();
        
        if(l1 == 0 || l2 == 0)
            return max(l1, l2);
        
        vector<vector<int> > vvi(l1 + 1, vector<int>(l2 + 1, 0));
        
        for(int i = 0; i <= l1; ++ i)
            vvi[i][0] = i;
        for(int j = 0; j <= l2; ++ j)
            vvi[0][j] = j;
        
        for(int i = 1; i <= l1; ++ i)
            for(int j = 1; j <= l2; ++ j)
                if(word1[i - 1] == word2[j - 1])
                    vvi[i][j] = vvi[i - 1][j - 1];
                else
                    vvi[i][j] = min(min(vvi[i - 1][j], vvi[i][j - 1]), vvi[i - 1][j - 1]) + 1;
        
        return vvi[l1][l2];
    }
};

这里只是简单实现了动态规划的思路，如想详细研究，请看这pdf。