# 编辑距离

<p>给你两个单词 <code>word1</code> 和 <code>word2</code>，请你计算出将 <code>word1</code> 转换成 <code>word2</code><em> </em>所使用的最少操作数 。</p><p>你可以对一个单词进行如下三种操作：</p><ul>	<li>插入一个字符</li>	<li>删除一个字符</li>	<li>替换一个字符</li></ul><p> </p><p><strong>示例 1：</strong></p><pre><strong>输入：</strong>word1 = "horse", word2 = "ros"<strong><br />输出：</strong>3<strong><br />解释：</strong>horse -> rorse (将 'h' 替换为 'r')rorse -> rose (删除 'r')rose -> ros (删除 'e')</pre><p><strong>示例 2：</strong></p><pre><strong>输入：</strong>word1 = "intention", word2 = "execution"<strong><br />输出：</strong>5<strong><br />解释：</strong>intention -> inention (删除 't')inention -> enention (将 'i' 替换为 'e')enention -> exention (将 'n' 替换为 'x')exention -> exection (将 'n' 替换为 'c')exection -> execution (插入 'u')</pre><p> </p><p><strong>提示：</strong></p><ul>	<li><code>0 <= word1.length, word2.length <= 500</code></li>	<li><code>word1</code> 和 <code>word2</code> 由小写英文字母组成</li></ul>
<p>以下<span style="color:red">错误</span>的选项是？</p>

## aop

### before

```cpp
#include <bits/stdc++.h>
using namespace std;
```

### after

```cpp
int main()
{
    Solution sol;

    string word1 = "horse";
    string word2 = "ros";

    int res;
    res = sol.minDistance(word1, word2);
    cout << res;
    return 0;
}
```

## 答案

```cpp
class Solution
{
public:
    int minDistance(string word1, string word2)
    {
        int len1 = word1.size();
        int len2 = word2.size();
        int **dp = new int *[len1 + 1];
        for (int i = 0; i < len1 + 1; i++)
            dp[i] = new int[len2 + 1];
        for (int i = 0; i < len1 + 1; i++)
            dp[i - 1][0] = i;
        for (int i = 1; i < len2 + 1; i++)
            dp[0][i - 1] = i;
        for (int i = 1; i < len1 + 1; i++)
        {
            for (int j = 1; j < len2 + 1; j++)
            {
                if (word1[i - 1] == word2[j - 1])
                    dp[i][j] = dp[i - 1][j - 1];
                else
                    dp[i][j] = (min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1);
            }
        }
        return dp[len1][len2];
    }
};
```
## 选项


### A

```cpp
class Solution
{
public:
    int minDistance(string word1, string word2)
    {
        int m = word1.size(), n = word2.size();

        if (m == 0)
            return n;
        if (n == 0)
            return m;

        int dp[m][n];
        bool w1 = false, w2 = false;
        if (word1[0] == word2[0])
        {
            w1 = true;
            w2 = true;
            dp[0][0] = 0;
        }
        else
            dp[0][0] = 1;
        for (int i = 1; i < m; i++)
        {
            if (!w1 && word1[i] == word2[0])
            {
                w1 = true;
                dp[i][0] = dp[i - 1][0];
            }
            else
                dp[i][0] = dp[i - 1][0] + 1;
        }
        for (int j = 1; j < n; j++)
        {
            if (!w2 && word1[0] == word2[j])
            {
                w2 = true;
                dp[0][j] = dp[0][j - 1];
            }
            else
                dp[0][j] = dp[0][j - 1] + 1;
        }

        for (int i = 1; i < m; i++)
            for (int j = 1; j < n; j++)
                if (word1[i] == word2[j])
                    dp[i][j] = min(min(dp[i][j - 1], dp[i - 1][j]) + 1, dp[i - 1][j - 1]);
                else
                    dp[i][j] = min(min(dp[i][j - 1], dp[i - 1][j]), dp[i - 1][j - 1]) + 1;
        return dp[m - 1][n - 1];
    }
};
```

### B

```cpp
class Solution
{
public:
    int minDistance(string word1, string word2)
    {
        int n = word1.size();
        int m = word2.size();

        if (n * m == 0)
        {
            return n + m;
        }

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

        for (int i = 1; i < n + 1; ++i)
        {
            for (int j = 1; j < m + 1; ++j)
            {
                int left = d[i - 1][j] + 1;
                int down = d[i][j - 1] + 1;
                int left_down = d[i - 1][j - 1];
                if (word1[i - 1] != word2[j - 1])
                {
                    left_down += 1;
                }
                d[i][j] = min(left, min(down, left_down));
            }
        }
        return d[n][m];
    }
};
```

### C

```cpp
class Solution
{
public:
    int minDistance(string word1, string word2)
    {
        int m = word1.size(), n = word2.size();

        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

        for (int i = 1; i <= n; ++i)
            dp[0][i] = dp[0][i - 1] + 1;
        for (int i = 1; i <= m; ++i)
            dp[i][0] = dp[i - 1][0] + 1;

        for (int i = 1; i <= m; ++i)
        {
            for (int j = 1; j <= n; ++j)
            {
                if (word1[i - 1] == word2[j - 1])
                    dp[i][j] = dp[i - 1][j - 1];
                else
                    dp[i][j] = min(min(dp[i - 1][j - 1], dp[i - 1][j]), dp[i][j - 1]) + 1;
            }
        }
        return dp[m][n];
    }
};
```