题解 | #编辑距离(一)#

//时间复杂度为O（n*m），空间复杂度为O（n*m）
int Min(int a,int b)
{
    if(a < b)
        return a;
    return b;
}

int editDistance(char* str1, char* str2 ) 
{
    // write code here
    int len1 = strlen(str1);
    int len2 = strlen(str2);
    int dp[len1+1][len2+1];//用dp[i][j]表示从两个字符串首部各自到str1[i]和str2[j]为止的子串需要的编辑距离
    dp[0][0] = 0;
    for(int i = 1; i < len1+1;i++)//假设第二个字符串为空，那很明显第一个字符串子串每增加一个字符，编辑距离就加1，这步操作是删除.
    {
        dp[i][0] = i;
    }
    for(int i = 1; i < len2+1;i++)//同理,假设第一个字符串为空,那第二个字符串每增加一个字符，编剧距离就加1，这步操作是添加。
    {
        dp[0][i] = i;
    }
    
    for(int i = 0; i < len1;i++)//将剩余的dp[i][j]填满
    {
        for(int j = 0;j < len2;j++)
        {
            if(str1[i] == str2[j])//如果遍历到str1[i]和 str2[j]的位置，这两个字符相同，这多出来的字符就不用操作，操作次数与两个子串的前一个相同
            {
                dp[i+1][j+1] = dp[i][j];
            }
            else//如果不相同
            {
                dp[i+1][j+1] = Min( dp[i][j], Min( dp[i+1][j],dp[i][j+1] ) ) + 1 ;
            }
        }
    }
    return dp[len1][len2];
}