C# Bottom-top DP O(n) space
\n# Code with O(nm) space\n\npublic class Solution {\n    public int MinDistance(string word1, string word2) {\n        var m = word1.Length;\n        var n = w
\n# Code with O(nm) space\n```\npublic class Solution {\n    public int MinDistance(string word1, string word2) {\n        var m = word1.Length;\n        var n = word2.Length;\n        var dp = new int[m+1, n+1];\n\n        for(var i = 0; i <= m; i++)\n        {\n            dp[i, 0] = i;\n        }\n\n        for(var j = 0; j <= n; j++)\n        {\n            dp[0, j] = j;    \n        }\n\n        for(var i = 0; i < m; i++)\n        {\n            for(var j = 0; j < n; j++)\n            {\n                if(word1[i] == word2[j])\n                {\n                    dp[i+1, j+1] = Min(dp[i, j], dp[i, j+1] + 1, dp[i+1, j] + 1);\n                }\n                else\n                {\n                    dp[i+1, j+1] = Min(dp[i, j], dp[i, j+1], dp[i+1, j]) + 1;\n                }\n            }\n        }\n\n        return dp[m, n];\n\n        int Min(params int[] arr)\n        {\n            return arr.Min();\n        }\n    }\n}\n```\n\n# Optimized Code with O(n) space\n```\npublic class Solution {\n    public int MinDistance(string word1, string word2) {\n        var m = word1.Length;\n        var n = word2.Length;\n        // var dp = new int[m+1, n+1];\n        var prevRow = new int[n+1];\n\n        // for(var i = 0; i <= m; i++)\n        // {\n        //     dp[i, 0] = i;\n        // }\n\n        for(var j = 0; j <= n; j++)\n        {\n            // dp[0, j] = j;    \n            prevRow[j] = j;\n        }\n\n        for(var i = 0; i < m; i++)\n        {\n            var curRow = new int[n+1];\n            curRow[0] = i + 1;\n\n            for(var j = 0; j < n; j++)\n            {\n                if(word1[i] == word2[j])\n                {\n                    // dp[i+1, j+1] = Min(dp[i, j], dp[i, j+1] + 1, dp[i+1, j] + 1);\n                    curRow[j+1] = Min(prevRow[j], prevRow[j+1] + 1, curRow[j] + 1);\n                }\n                else\n                {\n                    // dp[i+1, j+1] = Min(dp[i, j], dp[i, j+1], dp[i+1, j]) + 1;\n                    curRow[j+1] = Min(prevRow[j], prevRow[j+1], curRow[j]) + 1;\n                }\n            }\n            prevRow = curRow;\n        }\n\n        // return dp[m, n];\n        return prevRow[n];\n\n        int Min(params int[] arr)\n        {\n            return arr.Min();\n        }\n    }\n}\n```
['C#']