🔥Memoization + Tabulation + Space Optimization🔥 ||🔥DP||🔥C++ || Commented
Consider\uD83D\uDC4D\n\n                    Please Upvote If You Find It Helpful\n\n# Intuition\n    In this question we have to find the Minimum Operations to 
# Consider\uD83D\uDC4D\n```\n                    Please Upvote If You Find It Helpful\n```\n# Intuition\n    In this question we have to find the **Minimum Operations** to convert `word1` to `word2`.\n    So, what are the posibilities : \n        If both letters are equal then simply decrease index\n        Otherwise there are three posibilities:\n            We can `Insert` a letter\n            We can `Delete` a letter\n            We can `Replace` a letter\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n<!-- # Approach -->\n<!-- Describe your approach to solving the problem. -->\n\n<!-- # Complexity\n- Time complexity: -->\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n<!-- - Space complexity: -->\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n**Space Optimization**\n```\nclass Solution {\npublic:\n    // Space Optimization - TC: O(n * m), SC: O(m)\n    int minDistance(string word1, string word2) {\n    int n = word1.size(), m = word2.size();\n    // We make dp array 1 indexed\n    // Initialize two vectors to store the values of the previous and current rows of the dp array\n    vector<int> prev(m+1, 0), curr(m+1, 0);\n    // Initialize the first row of the dp array to the numbers 0, 1, 2, ..., m\n    for(int j=0;j<=m;j++) prev[j] = j;\n    // Iterate through each row of the dp array\n    for(int i=1;i<=n;i++){\n        // Set the first element of the current row to i\n        curr[0] = i;\n        // Iterate through each column of the dp array\n        for(int j=1;j<=m;j++){\n            // If the two characters are equal, no operation is needed\n            if(word1[i-1] == word2[j-1])\n                curr[j] = prev[j-1];\n            else {\n                // If the two characters are different, consider three possible operations:\n                // Insertion: add 1 to the minimum value among prev[j], curr[j-1], and prev[j-1]\n                curr[j] = 1 + min(prev[j], min(curr[j-1], prev[j-1]));\n            }\n        }\n        // Update the previous row to be equal to the current row\n        prev = curr;\n    }\n    // Return the value of the last element of the dp array, which represents the minimum edit distance\n    return prev[m];\n}\n};\n```\n**Tabulation**\n```\n// Tabulation - TC: O(n * m), SC: O(n * m)\n    int minDistance(string word1, string word2) {\n        int n = word1.size(), m = word2.size();\n        // We make dp array 1 indexed\n        vector<vector<int>> dp(n+1, vector<int>(m+1, 0));\n        for(int i=0;i<=n;i++) dp[i][0] = i;\n        for(int j=0;j<=m;j++) dp[0][j] = j;\n        for(int i=1;i<=n;i++){\n            for(int j=1;j<=m;j++){\n                if(word1[i-1] == word2[j-1]) dp[i][j] = dp[i-1][j-1];\n                else\n// Delete - dp[i-1][j], Insert - dp[i][j-1], Replace - dp[i-1][j-1]\n                    dp[i][j] = 1 + min(dp[i-1][j], \n        min(dp[i][j-1], dp[i-1][j-1]));\n            }\n        }\n        return dp[n][m];\n    }\n```\n**Memoization** \n```\n//Memoization - TC: O(n * m), SC: O(n * m) + O(n + m)\n    int find(string word1, string word2, int i, int j, vector<vector<int>>& dp){\n        if(j < 0) return i+1;\n        if(i < 0) return j+1;\n        if(dp[i][j] != -1) return dp[i][j];\n        if(word1[i] == word2[j]) return find(word1, word2, i-1, j-1, dp);\n        return dp[i][j] = 1 + min(find(word1, word2, i-1, j, dp), \n        min(find(word1, word2, i, j-1, dp), find(word1, word2, i-1, j-1, dp)));\n    }\n    int minDistance(string word1, string word2) {\n        int n = word1.size(), m = word2.size();\n        vector<vector<int>> dp(n+1, vector<int>(m+1, -1));\n        return find(word1, word2, n-1, m-1, dp);\n    }\n```\n```\n            Give a \uD83D\uDC4D. It motivates me alot\n```\nLet\'s Connect On [Linkedin](https://www.linkedin.com/in/naman-agarwal-0551aa1aa/)
['String', 'Dynamic Programming', 'C++']