https://leetcode-cn.com/problems/edit-distance/
# -*- coding:utf-8 -*- class Solution(object): def minDistance(self, word1, word2): """ :type word1: str :type word2: str :rtype: int """ n = len(word1) m = len(word2) # if one of the strings is empty if n * m == 0: return n + m # array to store the convertion history d = [[0] * (m + 1) for _ in range(n + 1)] # init boundaries for i in range(n + 1): d[i][0] = i for j in range(m + 1): d[0][j] = j # DP compute for i in range(1, n + 1): for j in range(1, m + 1): left = d[i - 1][j] + 1 down = d[i][j - 1] + 1 left_down = d[i - 1][j - 1] if word1[i - 1] != word2[j - 1]: left_down += 1 d[i][j] = min(left, down, left_down) return d[n][m] if __name__ == '__main__': word1 = "horse" word2 = "ros" print(Solution().minDistance(word1, word2))
思路:dp规则如下:
- 第一个单词的前i位变成第二个单词的前j-1位,然后再插入一个字符(d[i][j-1]+1)
- 第一个单词的前i-1位变成第二个单词的前j位,然后再删去一个字符(d[i-1][j]+1)
- 第一个单词的前i-1位变成第二个单词的前j-1位,然后替换最后一个字符,如果最后一个字符相同,即第一个单词的第i位和第二个单词的第j位相同的话,就不用替换了(d[i-1][j-1]),反之,如果不同就替换最后一位(d[i-1][j-1]+1)
0 条评论