Leetcode-Easy 72. Edit Distance

72. Edit Distance

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

• 思路： 动态规划
• 代码

代码语言：javascript复制

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]

distance edit 动态规划 字符串

0 人点赞