Edit Distance

This is a classic DP problem. Let $f(i, j)$ determine edit distance between character array $A[0...i-1]$ and $B[0...j-1]$ . Note that $f(0,x) = f(x, 0) = x$ . More ever, if $A[i - 1] == B[j - 1]$ , $f(i, j) = f(i-1, j-1)$ or else, $f(i, j) = \min(f(i-1,j-1), f(i-1, j), f(i, j-1)) + 1$ .

This can be implemented by used a 2D array and then building up the $f(i, j)$ table.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

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


int editDistance(char A[], int aEnd, char B[], int bEnd);

int main(void)
{
  char X[] = "str 1";
  char Y[] = "str 2";

  int lenX = strlen(X);
  int lenY = strlen(Y);

  printf("%d\n", editDistance(X, lenX, Y, lenY));
  return 0;
}

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

int editDistance(char A[], int aLen, char B[], int bLen)
{
  int memo[aLen + 1][bLen + 1];

  for(int i = 0; i <= aLen; i++)
  {
    memo[i][0] = i;
  }
  for(int j = 0; j <= bLen; j++)
  {
    memo[0][j] = j;
  }

  for(int i = 1; i <= aLen; i++)
  {
    for(int j = 1; j <= bLen; j++)
    {
      if(A[i] == B[j])
      {
        memo[i][j] = memo[i - 1][j - 1];
      }
      else
      {
        memo[i][j] = min(memo[i - 1][j - 1], memo[i - 1][j], memo[i][j - 1]) + 1;
      }
    }
  }

  return memo[aLen][bLen];
}