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]
分类: 算法

发表评论

电子邮件地址不会被公开。 必填项已用*标注