✅ Edit Distance, CPP, Recursive, Memoization, Top Down all approaches with explanation
\nThis problem is little bit tricky but don\'t worry we will solve it together.\nBasically, after reading the question carefully we can see that we have two cho
\nThis problem is little bit tricky but don\'t worry we will solve it together.\nBasically, after reading the question carefully we can see that **we have two choices, either the character will be same or not same**.\n\n* So, In the first choice, if the character will be same we don\'t have to do anything except for the fact that we have to call the function for the rest of the string.\n\n* For the second choice, if the character will not be the same we have three operations to do inorder to convert the word1 to word2\n\t1. Insert a character\n\t2. Delete a character\n\t3. Replace a character\n\nNow, Let\'s talk about the operations that we have to perform on word1, I\'m trying from the right side you can try from left also, depends on you.\n\n* So, for **Insert operation**, say for ex - we have two strings\n`s1 = "abc" , s2 = "bcd" , m = 3 , n = 3` **i.e.** \nlengths of the strings respectively `m` and `n` are pointing to the last characters of the string. So we will insert a character  from right side in `s1` and after inserting character string will be `"abcd"` and the `m` which  was pointing to `c` in `s1` will be at the same position but the `n` which was pointing to `d` in `s2` now, will point to `c` in `s2` i.e. `m, n-1` for the rest of the function calls.\n\n* Now, for **Delete operation**, same example\n`s1 = "abc", s2="bcd", m=3, n=3`\n`m` and `n` are pointing to the last characters of the string. Now, after deleting a character from `s1` , the `m` will be `m-1` , but the `n`  will be same i.e. `m-1, n`  for the rest of the function calls.\n\n* Now, for the **Replace operation**, same example\n`s1 = "abc", s2="bcd", m=3, n=3`\n`m` and `n` are pointing to the last characters of the string. Ultimately, the character at corresponding positions in strings will be the same after replacing the character in `s1` by\nthe character in `s2`, \n**Example** - `"abc", "bcd"` => replacing c by d => `"abd", "bcd"`\nNow, call for the rest of the string, so here `m` will be `m-1` and `n` will be `n-1` , i.e. `m-1, n-1` for the rest of the function calls.\n\nNow, we have to take minimum of all the three operations and add to 1\n\n* And Let\'s talk about **base conditions**\n**Example** - `s1 = "abc", s2 = "bcd", m=3, n=3`  lengths of strings respectively\n1. if `m = 0` , then Obviously, we have to insert `n`  characters from `s2`  in `s1`  to make `s2`. \n2. if `n = 0` , then Obviously, we have to delete `m`  characters in `s1`  to make `s2`.\n\n**Recursive**\n```\nclass Solution {\npublic:\n    //Time: O(min(3^m, 3^n)), Space: O(N);\n    int minDistance(string word1, string word2) {\n        int m = word1.length(), n = word2.length();\n        return editDistance(word1, word2, m, n);\n    }\n    \n    int editDistance(string& word1, string& word2, int m, int n){\n\t\t\n\t\t//base condition\n        if(m == 0) return n;\n        if(n == 0) return m;\n        \n        if(word1[m-1] == word2[n-1]) \n\t\t\treturn editDistance(word1, word2, m-1, n-1);\n        else{\n            int insertChar = editDistance(word1, word2, m, n-1);\n            int deleteChar = editDistance(word1, word2, m-1, n);\n            int replaceChar = editDistance(word1, word2, m-1, n-1);\n            \n            return 1 + min({insertChar, deleteChar, replaceChar});\n        }\n    }\n};\n```\n\n**Recursive + Memoization - TopDown**\n```\nclass Solution {\npublic:\n    //Time: O(m*n), Space: O(m*n);\n    int minDistance(string word1, string word2) {\n        int m = word1.length(), n = word2.length();\n        vector<vector<int>> memo(m+1, vector<int>(n+1, -1));\n        return editDistance(word1, word2, m, n, memo);\n    }\n    \n    int editDistance(string& word1, string& word2, int m, int n, vector<vector<int>>& memo){\n        if(m == 0) return memo[m][n] = n;\n        if(n == 0) return memo[m][n] = m;\n        \n        if(memo[m][n] != -1)\n            return memo[m][n];\n        \n        if(word1[m-1] == word2[n-1]) \n            return memo[m][n] = editDistance(word1, word2, m-1, n-1, memo);\n        else{\n            int insertChar = editDistance(word1, word2, m, n-1, memo);\n            int deleteChar = editDistance(word1, word2, m-1, n, memo);\n            int replaceChar = editDistance(word1, word2, m-1, n-1, memo);\n            \n            return memo[m][n] = 1 + min({insertChar, deleteChar, replaceChar});\n        }\n    }\n};\n```\n\n**BottomUp**\n```\nclass Solution {\npublic:\n    //Time: O(m*n), Space: O(m*n);\n    int minDistance(string word1, string word2) {\n        int m = word1.length(), n = word2.length();\n        vector<vector<int>> dp(m+1, vector<int>(n+1, 0));\n        \n        //Base conditions\n        for(int i=0; i<m+1; i++)\n            dp[i][0] = i;\n        \n        for(int j=0; j<n+1; j++)\n            dp[0][j] = j;\n        \n        //solving the sub-problems\n        for(int i=1; i<m+1; i++){\n            for(int j=1; j<n+1; j++){\n                if(word1[i-1] == word2[j-1])\n                    dp[i][j] = dp[i-1][j-1];\n                else{\n                    int insertChar = dp[i][j-1];\n                    int deleteChar = dp[i-1][j];\n                    int replaceChar = dp[i-1][j-1];\n                    \n                    dp[i][j] = 1 + min({insertChar, deleteChar, replaceChar});\n                }\n            }\n        }\n        return dp[m][n];\n    }\n};\n```
['Dynamic Programming', 'Recursion', 'Memoization', 'C', 'C++']