✅[C++] 3 STEPS SOLUTION | EASY-CONCISE | EXPLANATION & COMPLEXITIES✔️
THIS PROBLEM IS A VERY CLASSICAL PROBLEM OF DP\nEXPLANATION:\n1. THE IDEA IS VERY VERY SIMPLE, IF YOU UNDERSTAND THE RECURSIVE CODE LOGIC THEN, CONVERT IT INTO 
* ###  **THIS PROBLEM IS A VERY CLASSICAL PROBLEM OF DP**\n**EXPLANATION:**\n1. **`THE IDEA IS VERY VERY SIMPLE, IF YOU UNDERSTAND THE RECURSIVE CODE LOGIC THEN, CONVERT IT INTO DP IS CAKEWALK !!! :)`**\n\n1. **`IN THIS PROBLEM WE\'RE GIVEN A TWO STRINGS "Word1" && "Word2". WE NEED TO CONVERT FIRST STRING TO SECOND, WITH THE HELP OF THREE OPERATIONS (INSERT, DELETE, REPLACE)..`**\n\n1. **`STEP 1: WHEN BOTH CHARACTERS OF STRING MATCHES WE DO NOT HAVE TO DO ANYTHING (ANY OPERATIONS). JUST SIMPLY RECURR FOR NEXT ELEMENTS IN BOTH STRINGS`!**\n1. **`STEP 2: WHEN CHARACTERS DOESN\'T MATCH, WE NEED TO DO THREE OPERATIONS THAT IS`:**\n        **`a) INSERT :  editDist(w1, w2, n, m - 1) :- Decrement second string size, cuz we have to insert character according to second string`** \n        **`b) DELETE :  editDist(w1, w2, n - 1, m) :- Decrement first string size, cuz we to convert first string to second string =, by deleting characters`** \n        **`c) REPLACE : editDist(w1, w2, n - 1, m - 1) :- Again, decrement Both string size, cuz let assume we replaced the character of second string with the character                                                    of first string. Hence, both characters are same again.`**  \n1. **`STEP 3: TAKE THE MINIMUM OF THREE SUB-RESULTS.`**\n### **RECURSIVE SOLUTION :- T.L.E. (Not Accepted)**\n```\n// Recursive Code\nclass Solution {\npublic:\n    int editDist(string &w1, string &w2, int n, int m){\n        if(n == 0)                          // Base Case 1 : If first string is empty, simply return second string len. Because, we need atleast second\n            return m;                       //               string size or len to convert first into second\n        else if(m == 0)\n                return n;                   // Base Case2 2: Vice-Versa of above base case\n        else if(w1[n - 1] == w2[m - 1])\n               return editDist(w1, w2, n - 1, m - 1); //  when both characters are matched don\'t need to do any operations \n        else               \n            return 1 + min({editDist(w1, w2, n, m - 1), editDist(w1, w2, n - 1, m), editDist(w1, w2, n - 1, m - 1)});  // When characters Doesn\'t match \n    }                                                                                                          // we need to do Three Operations as \n    int minDistance(string word1, string word2) {                                                          // Mentioned Above & Take the minimum of them\n        int n = word1.size(), m = word2.size();\n        return editDist(word1, word2, n, m);\n    }\n};\n```\n**TIME COMPLEXITY : `O(3^N)`, Where, `N = (m + n)`, n : size of word1 & m  : size of word2** \n**SPACE COMPLEXITY : `O(constant)`, ignoring recusrion stack**\n```\n```\n### **DP SOLUTION: TOP-DOWN OR MEMOIZATION (Accepted)**\n* **Runtime : 10ms**\n```\n// Memoized Code (Top-Down)\nclass Solution {\npublic:\n    int editDist(string &w1, string &w2, int n, int m, vector<vector<int>>& memo){\n        if(n == 0)\n            return m;\n        if(m == 0)\n                return n;\n        if(memo[n][m] != -1)\n            return memo[n][m];\n        if(w1[n - 1] == w2[m - 1]){\n            memo[n][m] = editDist(w1, w2, n - 1, m - 1, memo); //  when both characters are matched don\'t need to do any operations\n            return memo[n][m];\n        }\n        else{               // When characters Doesn\'t match we need to do Three Operations as Mentioned Above & Take the minimum of them\n            memo[n][m] = 1 + min({editDist(w1, w2, n, m - 1, memo), editDist(w1, w2, n - 1, m, memo), editDist(w1, w2, n - 1, m - 1, memo)});\n            return memo[n][m];\n        }\n    }\n    int minDistance(string word1, string word2) {\n        int n = word1.size(), m = word2.size();\n        vector<vector<int>> memo(n + 1, vector<int> (m + 1, -1));\n        return editDist(word1, word2, n, m, memo);\n    }\n};\n```\n**TIME COMPLEXITY : `O(n * m)`, Where, n : size of word1 & m  : size of word2** \n**SPACE COMPLEXITY : `O(n * m)`, For using 2D array Aux space & Again, ignoring recusrion stack**\n```\n```\n### **DP SOLUTION: BOTTOM-UP OR TABULATION (Accepted)**\n* **Runtime : 4ms**\n```\n// Tabulation Code (Bottom-Up)\nclass Solution {\npublic:\n    int minDistance(string w1, string w2) {\n        int n = w1.size(), m = w2.size();\n        vector<vector<int>> dp(n + 1, vector<int> (m + 1, 0));\n        for(int i = 0; i <= n; ++i)     // Base Case 1:\n            dp[i][0] = i;\n        \n        for(int j = 0; j <=m; ++j)      // Base Case 2: \n            dp[0][j] = j;\n        \n        for (int i = 1; i <= n; ++i) {\n            for (int j = 1; j <= m; ++j) {\n                if(w1[i - 1] == w2[j - 1])          //  when both characters are matched don\'t need to do any operations\n                    dp[i][j] = dp[i - 1][j - 1];\n                else                               // When characters Doesn\'t match we need to do Three Operations as Mentioned Above & Take the minimum of them\n                    dp[i][j] = 1 + min({dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]});\n            }\n        }\n        return dp[n][m];\n    }\n};\n```\n**TIME COMPLEXITY : `O(n * m)`, Where, n : size of word1 & m  : size of word2** \n**SPACE COMPLEXITY :  `O(n * m)`, For using 2D array Aux space**\n\nif you find any mistakes pls, drop a comment\nif it makes any sense **Pls Upvote :)**
['Dynamic Programming']