Easy Solution
\n# Complexity\n- Time complexity:O(nm)\n Add your time complexity here, e.g. O(n) \n\n- Space complexity:O(nm)\n Add your space complexity here, e.g. O(n) \n\n
\n# Complexity\n- Time complexity:O(n*m)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:O(n*m)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    int minDistance(string word1, string word2) {\n        int n = word1.length(), m = word2.length();\n        vector<vector<int>> dp(n+1, vector<int>(m+1));\n\n        for(int i = 1; i<=n; i++){\n            dp[i][0] = i;\n        }\n        for(int i = 1; i<=m; i++){\n            dp[0][i] = i;\n        }\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                }\n                else{\n                    dp[i][j] = 1 + min(dp[i-1][j-1], min(dp[i-1][j], dp[i][j-1]));\n                }\n            }\n        }\n        return dp[n][m];\n    }\n};\n```
['C++']