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. <\/strong><\/p>\n\n\n\n There are 3 different types of operations you can perform on s1.<\/p>\n\n\n\n For example, if you are given the string s1 = \u201cfovutyor\u201d and the string s2 = \u201cfavtutor,\u201d you need a minimum of 3 characters to convert s1 to s2. <\/p>\n\n\n\n First, you use the replace character operation to replace \u2018o\u2019 with \u2018a\u2019; now the string becomes \u201cfavutyor.\u201d Second, you use the insert operation to insert ‘t’ at index 4; now the string becomes \u201cfavtutyor.\u201d At last, you use the erase operation to remove ‘y’. Now the string s1 is converted to s2.<\/p>\n\n\n\n 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.<\/p>\n\n\n\n Let\u2019s find out how to do it step-by-step:<\/p>\n\n\n\n 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).<\/p>\n\n\n\n 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.<\/p>\n\n\n\n Let us examine how we can convert the above approach into a memorized one:<\/p>\n\n\n\n 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.<\/p>\n\n\n\n In the above approach, we are consuming O(n*m) <\/strong>space which can be reduced if we store the previously computed values instead of storing all the values. Let\u2019s examine this approach step by step.<\/p>\n\n\n\n Let\u2019s examine the code for the above process.<\/p>\n\n\n\n We can implement this approach in C++ to solve the Edit Distance problem:<\/p>\n\n\n\n Here is the Java code to do it:<\/p>\n\n\n\n You can also use Python to implement it:<\/p>\n\n\n\n Output:<\/strong> <\/p>\n\n\n\n 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.<\/p>\n\n\n\n Here is a comparison of all the approaches:<\/p>\n\n\n\n\n
![\"Example](\"https:\/\/lh7-us.googleusercontent.com\/zY2soboav1KfF6VLJmZhA-fv-uP89JZoSl7b4NlEZRsO313tI438D8bHSES5P55kEQTgs7tu7hKKzVvrQHURjQ5u_hsGvAvermJ3RI4wbgW105RUeSm-z0yGjClXi2jVJOYB83kFoSk12kmetzqKVb0\")
![\"Replace](\"https:\/\/lh7-us.googleusercontent.com\/nN_yzHM8JNCAdPstSsDd8r8aqV1QTO8zIiG8GLbIwNwVwgMwElJ74Rsj9tuYBP0IjyrMDfZi7m0WC5giS-gZKWP5bRZzy9DLulxCMKjIf8YBma5tWwu0zfuv_mAPdMit9E7ww0GCAFy-ZacZnjljxnQ\")
![\"Insert](\"https:\/\/lh7-us.googleusercontent.com\/rCHegqODbpAcPnjcQ1I3Nv-Ql1KuSH-CLguFv92z-fx1ksVc4_Ob-1U3hf8e7cr-BSGgFeiE7zFNI6sv8BMgJm0yV3sdHL9tyZ5kQr_2m5sQ9ikmRl2xKmUbPeZdsd40lYKJXaLdqONpO3PX7HDm7HI\")
![\"Delete](\"https:\/\/lh7-us.googleusercontent.com\/unq-1wurUdwyCuYl_TaNE0HtqvPxseJ7QRne4glSKyf0jSKJ70FRNNYSHNavqr-PJwXIFwODDKTEqyHXb9ofWG9QpYAaWM7g7vZcGTXdPK5PLv-eNcNB-NKsfDnnnuLr2e5TZSZkm9a41Eorwyx2rmo\")
Brute Force Approach<\/strong><\/h2>\n\n\n\n
\n
Dynamic Programming Approach<\/strong><\/h2>\n\n\n\n
\n
Space Optimized Approach<\/strong><\/h2>\n\n\n\n
\n
C++ Code<\/strong><\/h3>\n\n\n\n
#include<bits\/stdc++.h>\nusing namespace std;\n\n int minDistance(string s1, string s2) {\n \n int n = s1.size(), m = s2.size();\n vector<int>prv(m+2,0);\n vector<int>curr(m+2,0);\n for(int i=0; i<=n; i++){\n for(int j=0; j<=m; j++){\n\n if(i == 0){\n curr[j] = j;\n }\n else if( j == 0 ){\n curr[j] = i;\n }\n else if (s1[i-1] == s2[j-1]){\n curr[j] = prv[j-1];\n }\n else{\n curr[j] = 1 + min({ curr[j-1], prv[j-1], prv[j] });\n }\n }\n prv = curr;\n }\n\n return curr[m];\n }\n \n\n int main(){\n string s1 = "fovutyor", s2 ="favtutor";\n int min_operations = minDistance(s1, s2);\n cout<<min_operations<<endl;\n return 0;\n }<\/pre><\/div>\n\n\n\nJava Code<\/strong><\/h3>\n\n\n\n
import java.util.Arrays;\n\nclass EditDistance {\n public static int minDistance(String s1, String s2) {\n int n = s1.length(), m = s2.length();\n int[] prv = new int[m+2];\n int[] curr = new int[m+2];\n \n for(int i = 0; i <= n; i++) {\n for(int j = 0; j <= m; j++) {\n if(i == 0) {\n curr[j] = j;\n } else if(j == 0) {\n curr[j] = i;\n } else if(s1.charAt(i-1) == s2.charAt(j-1)) {\n curr[j] = prv[j-1];\n } else {\n curr[j] = 1 + Math.min(Math.min(curr[j-1], prv[j-1]), prv[j]);\n }\n }\n prv = Arrays.copyOf(curr, curr.length);\n }\n \n return curr[m];\n }\n\n public static void main(String[] args) {\n String s1 = "fovutyor";\n String s2 = "favtutor";\n int min_operations = minDistance(s1, s2);\n System.out.println(min_operations);\n }\n}<\/pre><\/div>\n\n\n\nPython Code<\/strong><\/h3>\n\n\n\n
def minDistance(s1: str, s2: str) -> int:\n n = len(s1)\n m = len(s2)\n prv = [0] * (m + 2)\n curr = [0] * (m + 2)\n \n for i in range(n + 1):\n for j in range(m + 1):\n if i == 0:\n curr[j] = j\n elif j == 0:\n curr[j] = i\n elif s1[i - 1] == s2[j - 1]:\n curr[j] = prv[j - 1]\n else:\n curr[j] = 1 + min(curr[j - 1], prv[j - 1], prv[j])\n prv = curr[:]\n \n return curr[m]\n\nif __name__ == "__main__":\n s1 = "fovutyor"\n s2 = "favtutor"\n min_operations = minDistance(s1, s2)\n print(min_operations)<\/pre><\/div>\n\n\n\n
3<\/code><\/pre>\n\n\n\n