# Edit Distance — Variants

On my previous medium article, I talked about the edit distance pattern in DP. Now, we look at a problem lifted from Steven Skiena’s — `Algorithm Design Manual`

— variant of edit distance :

**8–1. Typists often make transposition errors exchanging neighbouring characters, such as typing setve when you mean steve. This requires two substitutions to fix under the conventional definition of edit distance. Incorporate a swap operation into our edit distance function, so that such neighbouring transposition errors can be fixed at the cost of one operation. **

**[1]**

So, from the looks of it — we need another `Action`

here — which would be TRANSPOSITION.

The recurrence relation for transposition would be :

cost[i][j] = 1 + cost[i -2][j-2], if (source[i] == destination[j-1] && source[i-1] == destination[j], i, j > 1

Now, `getEditDistanceCost`

will have one more condition added to it :

*if*( i > 1 && j > 1) {

*char *prevSource = source.charAt(i - 2);

*char *prevDestination = destination.charAt(j - 2);

*if*(chI == prevDestination && chJ == prevSource)

{

*if*(dp[i][j].cost > dp[i - 2][j - 2].cost + 1) {

dp[i][j].cost = dp[i - 2][j - 2].cost + 1;

dp[i][j].parent = Actions.TRANSPOSITION;

}

}

}

and we add in an additional action — transposition.