My clean java solution with O(n) space  in 17 lines
public class Solution {\n        public int minDistance(String word1, String word2) {\n            int[] d = new int[word2.length() + 1];\n            for (int 
    public class Solution {\n        public int minDistance(String word1, String word2) {\n            int[] d = new int[word2.length() + 1];\n            for (int i = 0; i <= word2.length(); ++i) d[i] = i;\n            for (int i = 1; i <= word1.length(); ++i) {\n                int prev = d[0];\n                d[0] = i;\n                for (int j = 1; j <= word2.length(); ++j) {\n                    int tmp = d[j];\n                    d[j] = Math.min(d[j - 1], d[j]) + 1;\n                    d[j] = Math.min(d[j], prev + (word1.charAt(i -1) == word2.charAt(j - 1) ? 0: 1));\n                    prev = tmp;\n                }\n            }\n            return d[word2.length()];\n        }\n    }
[]