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.
.
2 approaches to solve this problem are:
1) Recursive O(3^n)
2) Dynamic programming (tabular approach) O(n²)
Recursive approach (brute force )
The idea is to process all characters one by one starting from either from left or right sides of
both strings. Let us 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 (due to optimal substructure property) 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 implementation of above Naive recursive solution.
Recursive Code
what is the problem with this approach ??
Overlapping subproblems
We can see from the right side image that we have to solve
a given problem again and again in case of using a brute force approach. Due to this the
time complexity of this brute force approach is exponential. In worst case, we may end up
doing O(3^m) operations.
Tabulation Approach
Tabulation is the most optimized solution and works in a bottom-up approach
. Since it is quite clear that this problem has
dependencies on smaller problems discussed in the above section.
So, Before calculating eD(i,j) where eD is the editDistance function and i, j are the
respective indices pointer on the two strings, it would be good if we calculate eD(i,
j-1), eD(i-1, j) and eD(i-1, j-1). Refer to the image on right side
Step-by-Step Video Explanation
Complexity Analysis
Time Complexity: O(n²)
Space Complexity: O(n²).
