72. Edit Distance

相关资料

https://leetcode.com/problems/edit-distance/
https://www.cnblogs.com/easonliu/p/3661537.html
https://blog.csdn.net/baodream/article/details/80417695

Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2.

You have the following 3 operations permitted on a word:
1. Insert a character
2. Delete a character
3. Replace a character

解法

定义：d[i][j] 为 word1 前 i 个字符与 word2 前 j 个字符的最小编辑距离，则：
  d[i][0] = i;
  d[0][j] = j;
  d[i][j] = min(d[i-1][j]+1,d[i][j-1]+1,d[i-1][j-1]+cost)
其中：word1[i] == word2[j]，则 cost = 0，否则 cost = 1；

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int minDistance(char *s1, char *s2);
int min(int a, int b);

int main()
{
    char *s1 = "horse";
    char *s2 = "ros";

    int d = minDistance(s1,s2);

    printf("min edit distance is: %d\n", d);

    return 0;
}

int minDistance(char *s1, char *s2)
{
    int i,j;
    int cost = 0;
    int len1 = strlen(s1);
    int len2 = strlen(s2);
    int **d = (int **)malloc((len1+1)*sizeof(int *)); // 分配指针数组
    d[0] = (int *)malloc((len1+1)*(len2+1)*sizeof(int)); // 二维数组空间

    for(i = 1; i < (len1+1); i++)
    {
        d[i] = d[i-1] + (len2+1);
    }
    memset(d[0],0,(len1+1)*(len2+1)*sizeof(int));

    if (len1 == 0) return len2;
    if (len2 == 0) return len1;

    for (i = 1; i <= len1; i++)
    {
        d[i][0] = i;
    }
    for (j = 1; j <= len2; j++)
    {
        d[0][j] = j;
    }
    for (i = 1; i <= len1; i++)
    {
        for (j = 1; j <= len2; j++)
        {
            if (s1[i-1] == s2[j-1]) cost = 0;
            else cost = 1;

            d[i][j] = min(d[i-1][j]+1, min(d[i][j-1]+1, d[i-1][j-1]+cost));
        }
    }

    return d[len1][len2];
}

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