Python easy to understand DP solutions (O(m*n), O(n) space).
\nclass Solution(object):\n    # O(n) space\n    def minDistance(self, word1, word2):\n        h, w = len(word1)+1, len(word2)+1\n        pre = [i for i in rang
```\nclass Solution(object):\n    # O(n) space\n    def minDistance(self, word1, word2):\n        h, w = len(word1)+1, len(word2)+1\n        pre = [i for i in range(w)]\n        for i in range(1, h):\n            cur = [i for _ in range(w)]\n            for j in range(1, w):\n                cur[j] = min(pre[j-1]+(word1[i-1] != word2[j-1]), pre[j]+1, cur[j-1]+1)\n            pre = cur\n        return pre[-1]\n    \n    # O(m*n) space\n    def minDistance1(self, word1, word2):\n        h, w = len(word1)+1, len(word2)+1\n        dp = [[0 for _ in range(w)] for _ in range(h)]\n        for i in range(h):\n            dp[i][0] = i\n        for j in range(w):\n            dp[0][j] = j\n        for i in range(1, h):\n            for j in range(1, w):\n                dp[i][j] = min(dp[i-1][j-1]+(word1[i-1]!=word2[j-1]), dp[i-1][j]+1, dp[i][j-1]+1)\n        return dp[-1][-1]\n```
['Dynamic Programming', 'Python']