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

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] ?