Cpp Programming – Edit Distance

Given two strings str1 and str2 and below operations that can performed on str1. Find minimum number of edits (operations) required to convert ‘str1’ into ‘str2’.

• Insert
• Remove
• Replace

All of the above operations are of equal cost.

Examples:

Input:   str1 = "geek", str2 = "gesek"
Output:  1
We can convert str1 into str2 by inserting a 's'.

Input:   str1 = "cat", str2 = "cut"
Output:  1
We can convert str1 into str2 by replacing 'a' with 'u'.

Input:   str1 = "sunday", str2 = "saturday"
Output:  3
Last three and first characters are same.  We basically
need to convert "un" to "atur".  This can be done using
below three operations. 
Replace 'n' with 'r', insert t, insert a

[ad type=”banner”]

What are the subproblems in this case?
The idea is process all characters one by one staring from either from left or right sides of both strings.
Let we traverse from right corner, there are two possibilities for every pair of character being traversed.

m: Length of str1 (first string)
n: Length of str2 (second string)

• If last characters of two strings are same, nothing much to do. Ignore last characters and get count for remaining strings. So we recur for lengths m-1 and n-1.
• Else (If last characters are not same), we consider all operations on ‘str1’, consider all three operations on last character of first string, recursively compute minimum cost for all three operations and take minimum of three values.
  • Insert: Recur for m and n-1
  • Remove: Recur for m-1 and n
  • Replace: Recur for m-1 and n-1

Below is C++ implementation of above Naive recursive solution.

[pastacode lang=”cpp” manual=”%2F%2F%20A%20Naive%20recursive%20C%2B%2B%20program%20to%20find%20minimum%20number%0A%2F%2F%20operations%20to%20convert%20str1%20to%20str2%0A%23include%3Cbits%2Fstdc%2B%2B.h%3E%0Ausing%20namespace%20std%3B%0A%20%0A%2F%2F%20Utility%20function%20to%20find%20minimum%20of%20three%20numbers%0Aint%20min(int%20x%2C%20int%20y%2C%20int%20z)%0A%7B%0A%20%20%20return%20min(min(x%2C%20y)%2C%20z)%3B%0A%7D%0A%20%0Aint%20editDist(string%20str1%20%2C%20string%20str2%20%2C%20int%20m%20%2Cint%20n)%0A%7B%0A%20%20%20%20%2F%2F%20If%20first%20string%20is%20empty%2C%20the%20only%20option%20is%20to%0A%20%20%20%20%2F%2F%20insert%20all%20characters%20of%20second%20string%20into%20first%0A%20%20%20%20if%20(m%20%3D%3D%200)%20return%20n%3B%0A%20%0A%20%20%20%20%2F%2F%20If%20second%20string%20is%20empty%2C%20the%20only%20option%20is%20to%0A%20%20%20%20%2F%2F%20remove%20all%20characters%20of%20first%20string%0A%20%20%20%20if%20(n%20%3D%3D%200)%20return%20m%3B%0A%20%0A%20%20%20%20%2F%2F%20If%20last%20characters%20of%20two%20strings%20are%20same%2C%20nothing%0A%20%20%20%20%2F%2F%20much%20to%20do.%20Ignore%20last%20characters%20and%20get%20count%20for%0A%20%20%20%20%2F%2F%20remaining%20strings.%0A%20%20%20%20if%20(str1%5Bm-1%5D%20%3D%3D%20str2%5Bn-1%5D)%0A%20%20%20%20%20%20%20%20return%20editDist(str1%2C%20str2%2C%20m-1%2C%20n-1)%3B%0A%20%0A%20%20%20%20%2F%2F%20If%20last%20characters%20are%20not%20same%2C%20consider%20all%20three%0A%20%20%20%20%2F%2F%20operations%20on%20last%20character%20of%20first%20string%2C%20recursively%0A%20%20%20%20%2F%2F%20compute%20minimum%20cost%20for%20all%20three%20operations%20and%20take%0A%20%20%20%20%2F%2F%20minimum%20of%20three%20values.%0A%20%20%20%20return%201%20%2B%20min%20(%20editDist(str1%2C%20%20str2%2C%20m%2C%20n-1)%2C%20%20%20%20%2F%2F%20Insert%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20editDist(str1%2C%20%20str2%2C%20m-1%2C%20n)%2C%20%20%20%2F%2F%20Remove%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20editDist(str1%2C%20%20str2%2C%20m-1%2C%20n-1)%20%2F%2F%20Replace%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20)%3B%0A%7D%0A%20%0A%2F%2F%20Driver%20program%0Aint%20main()%0A%7B%0A%20%20%20%20%2F%2F%20your%20code%20goes%20here%0A%20%20%20%20string%20str1%20%3D%20%22sunday%22%3B%0A%20%20%20%20string%20str2%20%3D%20%22saturday%22%3B%0A%20%0A%20%20%20%20cout%20%3C%3C%20editDist(%20str1%20%2C%20str2%20%2C%20str1.length()%2C%20str2.length())%3B%0A%20%0A%20%20%20%20return%200%3B%0A” message=”C++” highlight=”” provider=”manual”/]

Output:

3

[ad type=”banner”]

The time complexity of above solution is exponential. In worst case, we may end up doing O(3^m) operations. The worst case happens when none of characters of two strings match. Below is a recursive call diagram for worst case.

We can see that many subproblems are solved again and again, for example eD(2,2) is called three times. Since same suproblems are called again, this problem has Overlapping Subprolems property. So Edit Distance problem has both properties (see this and this) of a dynamic programming problem. Like other typical Dynamic Programming(DP) problems, recomputations of same subproblems can be avoided by constructing a temporary array that stores results of subpriblems.

[pastacode lang=”cpp” manual=”%2F%2F%20A%20Dynamic%20Programming%20based%20C%2B%2B%20program%20to%20find%20minimum%0A%2F%2F%20number%20operations%20to%20convert%20str1%20to%20str2%0A%23include%3Cbits%2Fstdc%2B%2B.h%3E%0Ausing%20namespace%20std%3B%0A%20%0A%2F%2F%20Utility%20function%20to%20find%20minimum%20of%20three%20numbers%0Aint%20min(int%20x%2C%20int%20y%2C%20int%20z)%0A%7B%0A%20%20%20%20return%20min(min(x%2C%20y)%2C%20z)%3B%0A%7D%0A%20%0Aint%20editDistDP(string%20str1%2C%20string%20str2%2C%20int%20m%2C%20int%20n)%0A%7B%0A%20%20%20%20%2F%2F%20Create%20a%20table%20to%20store%20results%20of%20subproblems%0A%20%20%20%20int%20dp%5Bm%2B1%5D%5Bn%2B1%5D%3B%0A%20%0A%20%20%20%20%2F%2F%20Fill%20d%5B%5D%5B%5D%20in%20bottom%20up%20manner%0A%20%20%20%20for%20(int%20i%3D0%3B%20i%3C%3Dm%3B%20i%2B%2B)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20for%20(int%20j%3D0%3B%20j%3C%3Dn%3B%20j%2B%2B)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20If%20first%20string%20is%20empty%2C%20only%20option%20is%20to%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20isnert%20all%20characters%20of%20second%20string%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20(i%3D%3D0)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20dp%5Bi%5D%5Bj%5D%20%3D%20j%3B%20%20%2F%2F%20Min.%20operations%20%3D%20j%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20If%20second%20string%20is%20empty%2C%20only%20option%20is%20to%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20remove%20all%20characters%20of%20second%20string%0A%20%20%20%20%20%20%20%20%20%20%20%20else%20if%20(j%3D%3D0)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20dp%5Bi%5D%5Bj%5D%20%3D%20i%3B%20%2F%2F%20Min.%20operations%20%3D%20i%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20If%20last%20characters%20are%20same%2C%20ignore%20last%20char%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20and%20recur%20for%20remaining%20string%0A%20%20%20%20%20%20%20%20%20%20%20%20else%20if%20(str1%5Bi-1%5D%20%3D%3D%20str2%5Bj-1%5D)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20dp%5Bi%5D%5Bj%5D%20%3D%20dp%5Bi-1%5D%5Bj-1%5D%3B%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20If%20last%20character%20are%20different%2C%20consider%20all%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20possibilities%20and%20find%20minimum%0A%20%20%20%20%20%20%20%20%20%20%20%20else%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20dp%5Bi%5D%5Bj%5D%20%3D%201%20%2B%20min(dp%5Bi%5D%5Bj-1%5D%2C%20%20%2F%2F%20Insert%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20dp%5Bi-1%5D%5Bj%5D%2C%20%20%2F%2F%20Remove%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20dp%5Bi-1%5D%5Bj-1%5D)%3B%20%2F%2F%20Replace%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20return%20dp%5Bm%5D%5Bn%5D%3B%0A%7D%0A%20%0A%2F%2F%20Driver%20program%0Aint%20main()%0A%7B%0A%20%20%20%20%2F%2F%20your%20code%20goes%20here%0A%20%20%20%20string%20str1%20%3D%20%22sunday%22%3B%0A%20%20%20%20string%20str2%20%3D%20%22saturday%22%3B%0A%20%0A%20%20%20%20cout%20%3C%3C%20editDistDP(str1%2C%20str2%2C%20str1.length()%2C%20str2.length())%3B%0A%20%0A%20%20%20%20return%200%3B%0A%7D” message=”C++” highlight=”” provider=”manual”/]

Output:

3

Time Complexity: O(m x n)
Auxiliary Space: O(m x n)

Applications: There are many practical applications of edit distance algorithm, refer Lucene API for sample. Another example, display all the words in a dictionary that are near proximity to a given word\incorrectly spelled word.

[ad type=”banner”]