LeetCode72-编辑距离-C#实现

leetcode

题目:https://leetcode.com/submissions/detail/67380292/

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
Subscribe to see which companies asked this question

参考资料:

参考: http://blog.csdn.net/feliciafay/article/details/17502919
资料: 斯坦福大学自然语言处理第三课-编辑距离

分析:

• 动态规划
• 状态: dp[i,j] 表示 word1第i个字符与word2第j个字符的编辑距离
• 初始化:
  $$D(i,0) = i\\ D(0,j) = j$$
• 状态转移:
  $$dp[i][j] = min\left\{\begin{matrix} (删除一个)dp[i-1][j]+1\\ (增加一个)dp[i][j-1]+1\\ (修改一个)() => \left\{\begin{matrix} if(word1[i] == word2[j])\\dp[i-1][j-1]\\ else \\dp[i-1][j-1]+1 \end{matrix}\right. \end{matrix}\right.$$

上面的状态转移方程的含义是，D(i,j)的值，

• 要么是D(i-1, j)的操作完成之后删除一个字符(第1个单词的第i个字符)，
• 要么是D(i, j-1)的操作完成之后增加一个字符(第2个单词的第j个字符)，
• 要么是D(i-1, j-1)的操作完成自后替换一个字符(如果第1个单词的第i个字符和第2个单词的第j个字符不等)，
  或者是D(i-1, j-1)的操作完成自后什么也不做(如果第1个单词的第i个字符和第2个单词的第j个字符相等)

实现代码

public class Solution
{
    public int MinDistance(string word1, string word2)
    {
        int l1 = word1.Length;
        int l2 = word2.Length;
        int[,] dp = new int[l1+1, l2+1];
        for(int i=0; i<=l1; i++)
        {
            dp[i, 0] = i;
        }
        for (int j = 0; j <= l2; j++)
        {
            dp[0, j] = j;
        }
        for(int i=1; i<=l1; i++)
        {
            for(int j=1; j<=l2; j++)
            {
                int min = word2[j-1] == word1[i-1] ? 0 : 1;
                dp[i, j] = Math.Min(Math.Min(dp[i - 1, j] + 1, dp[i, j - 1] + 1), min+dp[i-1,j-1]);
            }
        }
        return dp[l1,l2];
    }
}