# Levenshtein distance (Edit distance)

Min operations to convert String A to String B.

Related to Longest common subsequence (LCS)

Operations are character-level

- Insert, Delete, replace, (transpose)

The edit distance from **dof** to **dog** is 1.

From **cat** to **act** is 2. (just 1 with transpose)

## Computing Edit Distance

```
E(i, j) = min { E(i, j-1) + 1
, E(i-1, j) + 1
, E(i-1, j-1) + m
}
where m | Pi != Tj = 1
| otherwise = 0
```