LeetCode 72. Edit Distance

题目：给定两个单词，将第一个单词转换成第二个单词，需要的最少的步数。其中：替换，删除，增加都算是一个步数。

思路：不知道为啥这题标为难，其实也是超级简单的题目，唯一需要动一点脑子的，就是删除的那个操作，第二个单词的下标是不需要往前移的。比较值得注意的一点是，如果用的元组来做dict的key，效率很低，有可能会超时，改为二维数组效率就会快很多了。

class Solution:
    def __init__(self):
        self.cache = []

    def minDistance(self, word1, word2):
        """
        :type word1: str
        :type word2: str
        :rtype: int
        """
        self.cache = [[0] * len(word2) for i in range(len(word1))]
        return self.dp(word1, word2, 0, 0)

    def dp(self, word1, word2, i, j):
        if i == len(word1) or j == len(word2):
            return len(word1[i:]) + len(word2[j:])
        elif self.cache[i][j] != 0:
            return self.cache[i][j]
        elif word1[i] == word2[j]:
            return self.dp(word1, word2, i + 1, j + 1)
        else:
            self.cache[i][j] = min(self.dp(word1, word2, i, j + 1) + 1,
                                   self.dp(word1, word2, i + 1, j) + 1,
                                   self.dp(word1, word2, i + 1, j + 1) + 1)
            return self.cache[i][j]