Edit Distance Problem (C++, Java, Python)

Dynamic programming is the most important topic in DSA, often asked in most technical interviews. It helps us reduce time complexity by storing previously computed values and using them whenever needed. In this article, we will discuss the problem of “Edit Distance,” which can be solved by using dynamic programming.

Edit Distance Problem Explained

In the Edit Distance problem, you are given two strings: string s1 and string s2. You must find out how many minimum numbers of operations are required such that string s1 is converted to string s2.

There are 3 different types of operations you can perform on s1.

• Insert a character.
• Erase a character.
• Replace a character.

For example, if you are given the string s1 = “fovutyor” and the string s2 = “favtutor,” you need a minimum of 3 characters to convert s1 to s2.

First, you use the replace character operation to replace ‘o’ with ‘a’; now the string becomes “favutyor.” Second, you use the insert operation to insert ‘t’ at index 4; now the string becomes “favtutyor.” At last, you use the erase operation to remove ‘y’. Now the string s1 is converted to s2.

Brute Force Approach

The naive way is to look at all the possible ways in which we can convert the string s1 to string s2 and find the one that takes a minimum number of operations. This can be done if we go to each index and perform all the tree operations i.e. insert, erase, and replace one by one, find the minimum among them, and return the answer.

Let’s find out how to do it step-by-step:

1. First, create a function that will return the minimum operations needed to convert string s1 to s2.
2. Now send the current index of strings s1 and s2 at first they both are 0.
3. Now check if any of the indexes have the same value as the size of their string.
4. If not, return the sum of the difference between both strings with their current index.
5. If not. check if the characters of both strings are the same at the given indexes.
6. If not, return the 1 + minimum value among all three operations.

The time complexity of the above solution is O(3^n) where n is the size of string s1. As at each index, we are performing 3 operations remove, replace, and delete which are laid to O(3^n) time complexity. The space complexity for the above code is O(1).

Dynamic Programming Approach

In the above approach, we observe that we are computing the minimum operations by performing all three operations on each index. This leads to a high time complexity as we might compute the same values repeatedly. Therefore, instead of computing the same values, we will store them in an array and then determine the minimum operations.

Let us examine how we can convert the above approach into a memorized one:

1. Create an array of size n*m where n is the size of string s1 and m is the size of s2.
2. Now initialize all the values in the array with -1.
3. Now, whenever you are computing any value, check if the array value at that index is -1 or not.
4. If not return the value which is stored in the array.
5. Otherwise, compute the value and store it in the array.

The time complexity of the above solution is O(n*m) where n is the size of string s1 and m is the size of s2. At each index, we are performing 3 operations remove, replace, and delete, and also storing those values into the array. The space complexity for the above code is O(n*m) as we are making the array to store the repeating values.

Space Optimized Approach

In the above approach, we are consuming O(n*m) space which can be reduced if we store the previously computed values instead of storing all the values. Let’s examine this approach step by step.

1. First, create two arrays prv and curr of size n+1 where n is the size of s1. Initialize all the values of the array with 0.
2. When the size of string 2 is 0. Then number of operations required is equal to the size of string s1.
3. When the size of string 1 is 0. Then number of operations required is equal to the size of string s2.
4. If both the characters are the same at given indexes then move forward by assigning the previous value.
5. If not find all the possible operations we can do.

Let’s examine the code for the above process.

C++ Code

We can implement this approach in C++ to solve the Edit Distance problem:

#include<bits/stdc++.h>
using namespace std;

    int minDistance(string s1, string s2) {
    
        int n = s1.size(), m = s2.size();
        vector<int>prv(m+2,0);
        vector<int>curr(m+2,0);
        for(int i=0; i<=n; i++){
            for(int j=0; j<=m; j++){

                if(i == 0){
                    curr[j] = j;
                }
                else if( j == 0 ){
                    curr[j] = i;
                }
                else if (s1[i-1] == s2[j-1]){
                    curr[j] = prv[j-1];
                }
                else{
                    curr[j] = 1 + min({ curr[j-1], prv[j-1], prv[j] });
                }
            }
            prv = curr;
        }

        return curr[m];
    }
    

    int main(){
        string s1 = "fovutyor", s2 ="favtutor";
        int min_operations = minDistance(s1, s2);
        cout<<min_operations<<endl;
        return 0;
    }

Java Code

Here is the Java code to do it:

import java.util.Arrays;

class EditDistance {
    public static int minDistance(String s1, String s2) {
        int n = s1.length(), m = s2.length();
        int[] prv = new int[m+2];
        int[] curr = new int[m+2];
        
        for(int i = 0; i <= n; i++) {
            for(int j = 0; j <= m; j++) {
                if(i == 0) {
                    curr[j] = j;
                } else if(j == 0) {
                    curr[j] = i;
                } else if(s1.charAt(i-1) == s2.charAt(j-1)) {
                    curr[j] = prv[j-1];
                } else {
                    curr[j] = 1 + Math.min(Math.min(curr[j-1], prv[j-1]), prv[j]);
                }
            }
            prv = Arrays.copyOf(curr, curr.length);
        }
        
        return curr[m];
    }

    public static void main(String[] args) {
        String s1 = "fovutyor";
        String s2 = "favtutor";
        int min_operations = minDistance(s1, s2);
        System.out.println(min_operations);
    }
}

Python Code

You can also use Python to implement it:

def minDistance(s1: str, s2: str) -> int:
    n = len(s1)
    m = len(s2)
    prv = [0] * (m + 2)
    curr = [0] * (m + 2)
    
    for i in range(n + 1):
        for j in range(m + 1):
            if i == 0:
                curr[j] = j
            elif j == 0:
                curr[j] = i
            elif s1[i - 1] == s2[j - 1]:
                curr[j] = prv[j - 1]
            else:
                curr[j] = 1 + min(curr[j - 1], prv[j - 1], prv[j])
        prv = curr[:]
    
    return curr[m]

if __name__ == "__main__":
    s1 = "fovutyor"
    s2 = "favtutor"
    min_operations = minDistance(s1, s2)
    print(min_operations)

Output: 

3

The time complexity for the above process is O(n*m) as we have two nested loops to check at all the indexes. The space complexity is reduced to O(n) as we are storing the previous value and using it whenever needed.

Here is a comparison of all the approaches:

Conclusion

In this article, we see how can we use dynamic programming to solve the Edit Distance problem from leetcode. This reduces our time and space complexity. Dynamic programming is one of the most important topics in DSA that’s why it is asked in most of the interviews.