题解 | #编辑距离(一)#

编辑距离(一)

https://www.nowcoder.com/practice/6a1483b5be1547b1acd7940f867be0da

#
# 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
#
# 
# @param str1 string字符串 
# @param str2 string字符串 
# @return int整型
#
class Solution:
    def editDistance(self , str1: str, str2: str) -> int:
        n , m = len(str1) , len(str2)
        dp = [[0]*(n) for _ in range(m)]
		#初始化
        if str1[0] != str2[0]:
            dp[0][0] = 1 
        for i in range(1,m):
            dp[i][0] = dp[i-1][0] + 1
        for i in range(1,n):
            dp[0][i] = dp[0][i-1] + 1
		#动态规划计算
        for i in range(1,m):
            for j in range(1,n):
                if str1[j] == str2[i]:
                    dp[i][j] = dp[i-1][j-1]
                else:
                    dp[i][j] = min(dp[i-1][j-1],dp[i-1][j],dp[i][j-1])+1
        return dp[m-1][n-1]

全部评论

相关推荐

不愿透露姓名的神秘牛友
07-07 18:05
哈哈哈哈哈感觉朋友找工作的已经疯掉了,直接上图
码农索隆:真老板娘:“我嘞个去,这不我当年的套路吗
点赞 评论 收藏
分享
强大的马里奥:不太可能,我校计算机硕士就业率99%
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务