Edit Distance Algorithm (variant of longest common sub-sequence)

Question

I'm working on a school assignment which is defined as a variant of the longest common subsequence problem and which is presented in the context of dynamic programming.

The problem is defined as follows:

suppose that you are making a spell-checker with suggestions for misspelled words. You would like to be able to find the words that are closest to the string of non-word letters that a user has input.

These words can differ from the typed string by

1. missing a letter
2. having an extra letter
3. having a letter replaced with another letter

the costs are:

$c_i$, the cost of an insert

$c_d$, the cost of a deletion

$c_r$, the cost of a replacement

with the intention of beginning with a recursive approach that can be converted into a dynamic program, the idea is to build up from substrings.

let T(j,k) denote minimum cost to transform 
substring A[1...j] to substring B[1...k]. 

then there are four ways to convert A[1...j] 
into B[1...k]

1. delete the jth character of A[1...j] and 
convert the first j-1 characters of A into the 
first k characters of B.  This equals cost cd + 
T(j-1, k)

2. convert the first j characters of A into the 
first k-1 characters of B, and insert a kth 
character into B[1...k-1].  This equals cost ci 
+ T(j, k-1)

3. replace the jth character of A with the kth 
character of B and convert the first j-1 
characters of A into the first k-1 characters 
of B.  This equals cost cr + T(j-1,k-1)

4. If characters A[j] = B[k], just convert 
A[1..(j-1)] into B[1..(k-1)]
This has cost T(j-1,k-1)


This can be written as a recursion equation, 
taking the minimum over all four alternatives 
at each step:

T(j,k) = minimum of:
    {    T(j-1, k) + cd
         T(j,k-1) + ci
        T(j-1,k-1) if A[j] = B[k]
      T(j-1, k-1) + cr if A[j] != B[k]
    }

The question is this: suppose we're to add a "swap" function which corrects two letter which are typed in the wrong order. How would we modify the euation for the cost of changing string A into string B if the the cost of a swap is $C_s$?

My thought is:

T(j-1, k+1) if A[j,k] = B[k,j] ?

Answer 1

the additional cost of adding a swap function should be:

T(j-2,k-2) + Cs , if A[j-1]=B[k],and A[j]=B[k-1]

I found the answer by studying the Damerau–Levenshtein distance modification of the classic edit distance problem.

Source: https://en.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_distance