No. 25 – Edit Distance

Reference: http://codercareer.blogspot.com/2011/12/no-25-edit-distance.html

Problem: Implement a function which gets the edit distance of two input strings. There are three types of edit operations: insertion, deletion and substitution. Edit distance is the minimal number of edit operations to modify a string from one to the other.

For example, the edit distance between “Saturday” and “Sunday” is 3, since the following three edit operations are required to modify one into the other:

  1. Saturday → Sturday (deletion of ‘a’)
  2. Sturday→ Surday (deletion of ‘t’)
  3. Surday → Sunday (substitution of ‘n’ for ‘r’)

There is no way to achieve it with fewer than three operations.

/* Copyleft: Ming Lin <minggr@gmail.com> */

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

int **alloc_two_d(int row, int col)
{
	int **two_d;
	int i, j;

	two_d = malloc(sizeof(int*) * row);
	for (i = 0; i < row; i++)
		two_d[i] = malloc(sizeof(int) * col);

	for (i = 0; i < row; i++)
		for (j = 0; j < col; j++)
			two_d[i][j] = -1;

	return two_d;
}

int edit_distance(char *str1, char *str2)
{
	int **array;
	int len1, len2;
	int i, j;

	len1 = strlen(str1);
	len2 = strlen(str2);
	array = alloc_two_d(len1+1, len2+1);

	for (i = 0; i <= len1; i++) {
		for (j = 0; j <= len2; j++) {
			if (i == 0)
				array[i][j] = j;
			else if (j == 0)
				array[i][j] = i;
			else {
				if (str1[i-1] == str2[j-1])
					array[i][j] = array[i-1][j-1];
				else {
					int min;	

					min = array[i-1][j];
					if (array[i][j-1] < min)
						min = array[i][j-1];
					if (array[i-1][j-1] < min)
						min = array[i-1][j-1];
					
					array[i][j] = min + 1;
				}
			}
		}
	}

	return array[len1][len2];
}

int main()
{
	char *str1 = "Saturday";
	char *str2 = "Sunday";

	printf("%d\n", edit_distance(str1, str2));

	return 0;
}

 

Leave a Reply