AC Python 212 ms DP solution, O(mn) time O(n) space
This is similar to the longest common subsequence problem. Dynamic programming is intuitive.\n\n    def minDistance(self, word1, word2):\n        if len(word1) 
This is similar to the longest common subsequence problem. Dynamic programming is intuitive.\n\n    def minDistance(self, word1, word2):\n        if len(word1) == 0 or len(word2) == 0:\n            return max(len(word1), len(word2))\n        dist = range(len(word2) + 1)\n        for i in xrange(len(word1)):\n            dist_ij, dist[0] = i, i + 1\n            for j in xrange(len(word2)):\n                if word1[i] == word2[j]:\n                    dist_ij, dist[j + 1] = dist[j + 1], dist_ij\n                else:\n                    dist_ij, dist[j + 1] = dist[j + 1], min(dist[j], dist[j + 1], dist_ij) + 1\n        return dist[-1]\n\n\n    # 1146 / 1146 test cases passed.\n    # Status: Accepted\n    # Runtime: 212 ms\n    # 96.23%\n\n\nThe relations of DP are\n\n    # keep the last char:      dist(i + 1, j + 1) = dist(i, j)\n    # insert the last char:    dist(i + 1, j + 1) = dist(i + 1, j) + 1\n    # replace the last char:   dist(i + 1, j + 1) = dist(i, j)     + 1\n    # remove the last char:    dist(i + 1, j + 1) = dist(i, j + 1) + 1
['Dynamic Programming', 'Python']