# Overview

Simple (no weights, no recorded edit transcript) DP-based computation of the edit distance (also known as Levenshtein distance) of two given strings S1 and S2 of lengths n and m with a time complexity of O(nm), the time to fill the DP table. See Gusfield, p. 215 for details and extensions.

# Implementation

We compute the edit distance of two strings using the standard DP approach: we find D(n,m) by computing all combinations of D(i,j) for i and j smaller than n,m. Initialize the table of height s1.length+1 and width s2.length+1:

```<<init>>=
int[][] dp = new int[s1.length() + 1][s2.length() + 1];
```

We fill each row, from left to right:

```<<nested_loop>>=
for (int i = 0; i < dp.length; i++) {
for (int j = 0; j < dp[i].length; j++) {
```

Fill the table with the initial values, based on the base conditions: D(i,0)=i and D(0,j)=j, resulting in row 0 filled with values from 0 to n-1 and column 0 with values 0 to m-1:

```<<base_conditions>>=
dp[i][j] = i == 0 ? j : j == 0 ? i : 0;
```

For the other values, perform the bottom-up simulation of the recurrence relation, the actual DP computation:

```<<recurrence>>=
if (i > 0 && j > 0) {
```

The best case: match, so we can take the diagonal value without further cost (we compare the strings at index-1 since the table is one position larger than the strings in height and width).

```<<match>>=
if (s1.charAt(i - 1) == s2.charAt(j - 1))
dp[i][j] = dp[i - 1][j - 1];
```

Else, we pick set the new optimal sub-solution to MIN(DP[i][j-1]+1,DP[i-1][j-1]+1,DP[i-1][j]+1), i.e. to the minimum result of the replace (diagonal), insert-into-s1/delete-from-s2 (horizontal), and delete-from-s1/insert-into-s2 (vertical) operations.

```<<mismatch>>=
else
dp[i][j] = Math.min(dp[i][j - 1] + 1, Math.min(
dp[i - 1][j - 1] + 1, dp[i - 1][j] + 1));
```

The result is stored in the bottom right cell of the DP table: the edit distance for pair n,m: D(n,m).

```<<result>>=
return dp[s1.length()][s2.length()];
```

Compute the edit distance for some samples, including empty strings:

```<<usage>>=
EditDistance distance = new EditDistance();
System.out.println(distance.compute("vintner", "writers"));
System.out.println(distance.compute("vintners", "writers"));
System.out.println(distance.compute("vintners", ""));
System.out.println(distance.compute("", ""));
```

The complete program:

```<<EditDistance.java>>=
public class EditDistance {
public int compute(String s1, String s2) {
init
nested_loop
base_conditions
recurrence
match
mismatch
}
}
}
result
}
public static void main(String[] args) {
usage
}
}
```

# References

• Gusfield, Dan (1999), Algorithms on Strings, Sequences and Trees. Cambridge: University Press.