Leetcode-Easy 72. Edit Distance

简介: Leetcode-Easy 72. Edit Distance

72. Edit Distance


  • 描述:
    求两个字符串的编辑距离

    7.png
  • 思路:
    动态规划
  • 代码

class Solution:
     def  minDistance(self, strWord1, strWord2):
        res = [[0]*(len(strWord2)+1) for _ in range(len(strWord1)+1)]
        # handle extreme conditions first
        res[len(strWord1)][len(strWord2)] = 0
        for j in range(len(strWord2)+1):
            res[len(strWord1)][j] = len(strWord2)-j
        for i in range(len(strWord1)+1):
            res[i][len(strWord2)] = len(strWord1)-i
        for i in range(len(strWord1), -1, -1):
            for j in range(len(strWord2), -1, -1):
                if i == len(strWord1) or j == len(strWord2):
                    continue
                d = 0    
                if strWord1[i]==strWord2[j]:
                    d = res[i+1][j+1]
                else:
                    d = min(res[i][j+1], res[i+1][j], res[i+1][j+1]) + 1 
                res[i][j] = d    
        return res[0][0]


相关文章
|
数据库 C语言
LeetCode 72. Edit Distance
给定两个单词word1和word2,找到将word1转换为word2所需的最小操作数。 您对单词允许以下3个操作: 插入一个字符 删除一个字符 替换一个字符
48 0
LeetCode 72. Edit Distance
Leetcode-Easy 461.Hamming Distance
Leetcode-Easy 461.Hamming Distance
93 0
Leetcode-Easy 461.Hamming Distance
LeetCode之Hamming Distance
LeetCode之Hamming Distance
104 0