题解 | #计算字符串的编辑距离#

#include <stdio.h>

static int min(int a, int b, int c)
{
    a = (a < b)?a:b;
    a = (a < c)?a:c;
    return a;
}

static void ParseStr(char* str1, char* str2)
{
    if(!str1 || !str2)
    {
        printf("input failed!!!\n");
        return;
    }
    int len1 = strlen(str1);
    int len2 = strlen(str2);
    int dp[len1+1][len2+1];
    memset(dp, 0, (len1+1)*(len2+1)*sizeof(int));
    
    for(int i = 1; i < len1+1; i++)
    {
        dp[i][0] = i;
    }
    for(int i = 1; i < len2+1; i++)
    {
        dp[0][i] = i;
    }
    
    for(int i = 1; i < len1+1; i++)
    {
        for(int j = 1; j < len2+1; j++)
        {
            if(str1[i-1] == str2[j-1])
            {
                dp[i][j] = dp[i-1][j-1];
            }
            else
            {
                dp[i][j] = min(dp[i-1][j-1], dp[i][j-1], dp[i-1][j]) + 1;
            }
        }
    }
    
    /*for(int i = 0; i < len1+1; i++)
    {
        for(int j = 0; j < len2+1; j++)
        {
            printf("dp[%d][%d] = %d  ", i, j, dp[i][j]);
        }
        printf("\n");
    }*/
    
    printf("%d\n", dp[len1][len2]);
    return;
}

int main()
{
    char str1[1000] = {0};
    char str2[1000] = {0};
    gets(str1);
    gets(str2);
    ParseStr(str1, str2);
    return 0;
}

for(int i = 1; i < len1+1; i++)
{
	for(int j = 1; j < len2+1; j++)
	{
		if(str1[i-1] == str2[j-1])		//str1[0] = 'a',str2[0] = 'a' dp[1][1] = dp[0][0] = 1
		{
			dp[i][j] = dp[i-1][j-1];
		}
		else
		{
			dp[i][j] = min(dp[i-1][j-1], dp[i][j-1], dp[i-1][j]) + 1;
		}
	}
}

//dp[0][1] = (dp[0][0], dp[1][0], dp[0][1]) + 1 = 1

abcdefg
ablcdef

dp[0][0] = 0  dp[0][1] = 1  dp[0][2] = 2  dp[0][3] = 3  dp[0][4] = 4  dp[0][5] = 5  dp[0][6] = 6  dp[0][7] = 7  
dp[1][0] = 1  dp[1][1] = 0  dp[1][2] = 1  dp[1][3] = 2  dp[1][4] = 3  dp[1][5] = 4  dp[1][6] = 5  dp[1][7] = 6  
dp[2][0] = 2  dp[2][1] = 1  dp[2][2] = 0  dp[2][3] = 1  dp[2][4] = 2  dp[2][5] = 3  dp[2][6] = 4  dp[2][7] = 5  
dp[3][0] = 3  dp[3][1] = 2  dp[3][2] = 1  dp[3][3] = 1  dp[3][4] = 1  dp[3][5] = 2  dp[3][6] = 3  dp[3][7] = 4  
dp[4][0] = 4  dp[4][1] = 3  dp[4][2] = 2  dp[4][3] = 2  dp[4][4] = 2  dp[4][5] = 1  dp[4][6] = 2  dp[4][7] = 3  
dp[5][0] = 5  dp[5][1] = 4  dp[5][2] = 3  dp[5][3] = 3  dp[5][4] = 3  dp[5][5] = 2  dp[5][6] = 1  dp[5][7] = 2  
dp[6][0] = 6  dp[6][1] = 5  dp[6][2] = 4  dp[6][3] = 4  dp[6][4] = 4  dp[6][5] = 3  dp[6][6] = 2  dp[6][7] = 1  
dp[7][0] = 7  dp[7][1] = 6  dp[7][2] = 5  dp[7][3] = 5  dp[7][4] = 5  dp[7][5] = 4  dp[7][6] = 3  dp[7][7] = 2  
2


abcdefg
ablmncdef
dp[0][0] = 0  dp[0][1] = 1  dp[0][2] = 2  dp[0][3] = 3  dp[0][4] = 4  dp[0][5] = 5  dp[0][6] = 6  dp[0][7] = 7  dp[0][8] = 8  dp[0][9] = 9  
dp[1][0] = 1  dp[1][1] = 0  dp[1][2] = 1  dp[1][3] = 2  dp[1][4] = 3  dp[1][5] = 4  dp[1][6] = 5  dp[1][7] = 6  dp[1][8] = 7  dp[1][9] = 8  
dp[2][0] = 2  dp[2][1] = 1  dp[2][2] = 0  dp[2][3] = 1  dp[2][4] = 2  dp[2][5] = 3  dp[2][6] = 4  dp[2][7] = 5  dp[2][8] = 6  dp[2][9] = 7  
dp[3][0] = 3  dp[3][1] = 2  dp[3][2] = 1  dp[3][3] = 1  dp[3][4] = 2  dp[3][5] = 3  dp[3][6] = 3  dp[3][7] = 4  dp[3][8] = 5  dp[3][9] = 6  
dp[4][0] = 4  dp[4][1] = 3  dp[4][2] = 2  dp[4][3] = 2  dp[4][4] = 2  dp[4][5] = 3  dp[4][6] = 4  dp[4][7] = 3  dp[4][8] = 4  dp[4][9] = 5  
dp[5][0] = 5  dp[5][1] = 4  dp[5][2] = 3  dp[5][3] = 3  dp[5][4] = 3  dp[5][5] = 3  dp[5][6] = 4  dp[5][7] = 4  dp[5][8] = 3  dp[5][9] = 4  
dp[6][0] = 6  dp[6][1] = 5  dp[6][2] = 4  dp[6][3] = 4  dp[6][4] = 4  dp[6][5] = 4  dp[6][6] = 4  dp[6][7] = 5  dp[6][8] = 4  dp[6][9] = 3  
dp[7][0] = 7  dp[7][1] = 6  dp[7][2] = 5  dp[7][3] = 5  dp[7][4] = 5  dp[7][5] = 5  dp[7][6] = 5  dp[7][7] = 5  dp[7][8] = 5  dp[7][9] = 4  
4