The Edit Distance problem, also known as the Levenshtein distance, is the measure of the difference between two strings. The problem involves finding the minimum number of operations (insertions, deletions, or substitutions) required to transform one string into another.
Dynamic programming is a popular technique used to solve the Edit Distance problem. The approach involves building a matrix of size (m+1) x (n+1), where m and n are the lengths of the two strings. The rows and columns of the matrix represent the characters of the two strings, and each cell stores the minimum number of operations required to transform the substring of the first string ending at that position into the substring of the second string ending at that position.
The following steps describe the dynamic programming solution to the Edit Distance problem:
Initialize the first row and column of the matrix with the values from 0 to n and 0 to m, respectively, representing the cost of converting an empty string into a substring of the two strings.
For each cell (i,j) in the matrix, compute the minimum value of the following three cases: a. If the ith character of the first string is equal to the jth character of the second string, the cost of transforming the two substrings is the same as the cost of transforming the substrings ending at (i-1,j-1). b. If the ith character of the first string is different from the jth character of the second string, the cost of transforming the two substrings is the minimum of the cost of inserting, deleting, or substituting the ith character of the first string to match the jth character of the second string, plus the cost of transforming the substrings ending at (i-1,j-1). c. If either i or j is zero, the cost of transforming one of the substrings into an empty string is equal to the length of the other substring.
The final value in the bottom-right corner of the matrix represents the minimum number of operations required to transform the first string into the second string.
The time complexity of the dynamic programming solution to the Edit Distance problem is O(mn), where m and n are the lengths of the two strings. This is because the matrix of size (m+1) x (n+1) needs to be filled in one pass, and each cell requires a constant amount of time to compute.
An example of the dynamic programming solution to the Edit Distance problem for the two strings "kitten" and "sitting" is shown below:
| | s | i | t | t | i | n | g |
|---|---|---|---|---|---|---|---|
| | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| k | 1 | 1 | 2 | 3 | 4 | 5 | 6 |
| i | 2 | 1 | 2 | 3 | 4 | 5 | 6 |
| t | 3 | 2 | 1 | 2 | 3 | 4 | 5 |
| t | 4 | 3 | 2 | 1 | 2 | 3 | 4 |
| e | 5 | 4 | 3 | 2 | 2 | 3 | 4 |
| n | 6 | 5 | 4 | 3 | 3 | 2 | 3 |