C++ Well Commented Solution [With Explanation] [DP]
\nclass Solution\n{\npublic:\n    int minDistance(string word1, string word2);\n};\n\n/* Returns the minimum edit distance between the 2 strings */\nint Solutio
```\nclass Solution\n{\npublic:\n    int minDistance(string word1, string word2);\n};\n\n/* Returns the minimum edit distance between the 2 strings */\nint Solution :: minDistance(string str_1, string str_2)\n{\n    // Store the length of the two strings\n    int lenFirst = str_1.length();\n    int lenSecond = str_2.length();\n    \n    // Make a 2d vector of (len_first+1)*(len_second+1), since we are going to access the [len_first][len_second] element\n    vector<vector<int>> dp;\n    \n    // Resize the vector to appropriate dimensions and initialise it with zero\n    dp.resize(lenFirst+1);\n    for(auto &row_vec : dp)\n        row_vec.resize(lenSecond+1);\n    \n    /* DP definitions */\n    /* dp[i][j] returns the edit distance of the first i elements of str_1 and first j elements of str_2 */\n    \n    \n    /* dp[0][0] = 0\n     * dp[0][j] = j First string is empty,  only insertions can happen\n     * dp[i][0] = i Second string is empty, only deletions can happen\n     * Compactly, dp[i][j] = max(i,j) if one of them is zero\n     */\n    \n    // Fill the rest of the matrix \n    for(int i=0; i<=(lenFirst); i++)\n    {\n        for(int j=0; j<=(lenSecond); j++)\n        {\n            // Base case, as discussed above\n            if(i==0 || j==0)\n                dp[i][j] = max(i,j);\n                \n            // If the last characters match, just remove them and calclulate for the left half\n            else if(str_1[i-1] == str_2[j-1]) dp[i][j] = dp[i-1][j-1];\n            \n            // Else, the last character doesn\'t match\n            else\n            {\n                // Insert a new matching character at the end of first string. The last character matches now. \n                int insert = 1 + dp[i][j-1];\n                \n                // Delete the last character of the first string\n                int _delete = 1 + dp[i-1][j];\n                \n                // Replace the last character of the first string. Now, the last character matches. \n                int replace = 1 + dp[i-1][j-1];\n                \n                // Take the best possible of all outcomes\n                dp[i][j] = min({insert, _delete, replace});\n            }\n        }\n    }\n    \n    // Return the edit distance of str_1 and str_2\n    return dp[lenFirst][lenSecond];\n    \n}\n```
[]