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.