Java | TC: O(MN) | SC: O(min(M,N)) | Space Optimized DP Solution
java\n/**\n * Space Optimized Dynamic Programming solution\n *\n * dp[i][j] = the minimum number of operations to convert word1[0 .. i-1] to word2[0 .. j-1]\n *
```java\n/**\n * Space Optimized Dynamic Programming solution\n *\n * dp[i][j] = the minimum number of operations to convert word1[0 .. i-1] to word2[0 .. j-1]\n *\n * Time Complexity: O(M * N)\n *\n * Space Complexity: O(min(M, N)).\n *\n * M = Length string word1. N = Length of string word2.\n */\nclass Solution {\n    public int minDistance(String word1, String word2) {\n        if (word1 == null || word2 == null) {\n            throw new IllegalArgumentException("Input strings are null");\n        }\n\n        int insertCost = 1;\n        int deleteCost = 1;\n        int replaceCost = 1;\n        int l1 = word1.length();\n        int l2 = word2.length();\n\n        if (l1 == 0) {\n            return l2 * insertCost;\n        }\n        if (l2 == 0) {\n            return l1 * deleteCost;\n        }\n        // Bellow condition can be used only if all three costs are same.\n        if (l1 > l2) {\n            return minDistance(word2, word1);\n        }\n\n        int[] dp = new int[l1 + 1];\n        // Setting DP array for 0th column of 2D DP array. Here l2 is blank, thus we\n        // have to delete everything in l1.\n        for (int i = 1; i <= l1; i++) {\n            dp[i] = dp[i - 1] + deleteCost;\n        }\n\n        for (int j = 1; j <= l2; j++) {\n            int prev = dp[0];\n            dp[0] += insertCost; // l1 is blank, Inserting l2 chars in l1.\n            char c2 = word2.charAt(j - 1);\n            for (int i = 1; i <= l1; i++) {\n                char c1 = word1.charAt(i - 1);\n                int temp = dp[i];\n                // Both chars are same, so the distance will also remain same as dp[i-1][j-1]\n                if (c1 == c2) {\n                    dp[i] = prev;\n                } else {\n                    // Replace l1[i - 1] by l2[j - 1] ==> dp[i][j] = dp[i - 1][j - 1] + 1\n                    // Delete l1[i-1] from l1[0..i-1] ==> dp[i-1][j] + 1\n                    // Insert l2[j-1] into l1[0..i-1] ==> dp[i][j-1] + 1\n                    dp[i] = Math.min(prev + replaceCost, Math.min(dp[i - 1] + deleteCost, dp[i] + insertCost));\n                }\n                prev = temp;\n            }\n        }\n\n        return dp[l1];\n    }\n}\n```\n\n---\n\nSolutions to other similar questions on LeetCode:\n- [221. Maximal Square](https://leetcode.com/problems/maximal-square/discuss/1519235/Java-or-TC:-O(MN)-or-SC:-O(min(MN))-or-Space-optimized-DP-solution)\n- [161. One Edit Distance](https://leetcode.com/problems/one-edit-distance/discuss/1519249/Java-or-TC:-O(min(ST))-or-SC:-O(min(ST))-or-Optimal-One-Pass-solution)\n
['String', 'Dynamic Programming', 'Java']