Optimized C++ Approach
Intuition\n Describe your first thoughts on how to solve this problem. \nFor each index in string S1, there are three options for matching that index with strin
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nFor each index in string S1, there are three options for matching that index with string S2. Replace a character, delete a character, or insert a character at its index. So you can think in terms of string match paths. With no consistent data, there\'s no way to find out other than trying all possible methods. To do this, you have to use recursion.\n\n**Step 1: Index the problem**:\n\n>  We need two indices for iterating over both the strings.\n\n\n**Step 2: Try all possible options given the index.**\n\n> We have the cases of MATCH and MISMATCH\n\n1. MATCH: If the i and the j characters of word1 and word2 match, then we must reduce both the indices and calculate the solution for f(i-1,j-1)\n2. MISMATCH : If the i and the j characters of word1 and word2 mismatch, then we  have three possiblities: \n      - **Insert**: We insert word2[j] in word1 at position i and thus call the function f(i, j-1).\n      - **Delete**: We delete the word1[i] character and thus call the function f(i-1,j).\n      - **Replace**: We simply replace the word1[i] with word2[j], thus we should call f(i-1,j-1).\n\n**Step 3: Return the minimum value of all choices.**\n1. MATCH: return f(i-1,j-1)\n2. MISMATCH: return 1 + min({f(i-1,j), f(i,j-1), f(i-1,j-1)})\n\n#### BASE CASES\n\n1. if i<0 then return j;\n2. if j<0 then return i;\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nWe can memoize the above recursive formula, but we will use Tabulation to avoid extra recursive stack space and Recursion Overhead.\n\n> In order to implement the Tabulation, we need to take care of the negative indices. Thus we shift ourselves to 1-based indexing.\n\nPROCEDURE:\n\n1. We initialise a 2D vector with the first col filled with the row numbers and the first row filled with row numbers.\n2. Fill the matrix using the recursive formulation.\n3. Return dp[n][m] as the answer.\n\n# Complexity\n- Time complexity: $$O(n^2)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(n^2)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\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,0));\n        for(int row = 1;row<=n;row++)\n            dp[row][0] = row;\n        for(int col = 1;col<=m;col++)\n            dp[0][col] = col;\n        for(int i = 1;i<=n;i++){\n            for(int j = 1;j<=m;j++){\n                if(word1[i-1] == word2[j-1])\n                    dp[i][j] = dp[i-1][j-1];\n                else\n                    dp[i][j] = 1 + min({dp[i-1][j], dp[i-1][j-1], dp[i][j-1]});\n            }\n        }\n        return dp[n][m];\n    }\n};\n```
['String', 'Dynamic Programming', 'C++']