最短编辑距离

题目

给定两个字符串s1 和 s2, 计算出将s1转换成s2所使用的最少操作数。
你可对一个字符串进行如下三种操作

1. 插入一个字符
2. 删除一个字符
3. 替换一个字符

---

class MinEditDistance
{
    //递归 自顶向下
    string str1;
    string str2;
    public int GetMinEditDistance(strign str1,string str2)
    {
        this.str1 = str1;
        this.str2 = str2;

        return MinDis(str1.Length-1,str2.Length-1);
    }

    public int MinDis(int i,int j)
    {
        if(i < 0) return j+1;
        if(j < 0) return i+1;

        if(str[i]==str[j])
            return MinDis(i-1,j-1);
        else
        {
            return Min(MinDis(i,j-1)+1,MinDis(i-1,j)+1,MinDis(i-1,j-1)+1);            
        }
    }

    public int Min(int a,int b,int c)
    {
        int min = a;
        if(b<min)
            min = b;
        if(c<min)
            min = c;
        return min;
    }

//自底向上
    int[,] dp;
    public int CalMinDis(string str1,string str2)
    {
        this.str1 = str1;
        this.str2 = str2;
        dp = new int[str1.Length+1,str2.Length+1];
        dp[0,0] = 0;
        for(int i=1; i<=str1.Length; i++)
        {
            dp[i,0] = i;
        }
        for(int i=1; i<=str2.Length; i++)
        {
            dp[0,i] = i;
        }

        for(int i=1; i<=str1.Length; i++)
        {
            for(int j=1; j<=str2.Length; j++)
            {
                if(str1[i-1]==str2[j-1])
                    dp[i,j] = dp[i-1,j-1];
                else
                {
                    dp[i,j] = Min(dp[i,j-1]+1, dp[i-1,j]+1, dp[i-1,j-1]+1);
                }
            }
        }

        return dp[str1.Length;str2.Length];
    }

}