编辑距离(一)

[编程题]编辑距离(一)

热度指数：23821 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定两个字符串 str1 和 str2 ，请你算出将 str1 转为 str2 的最少操作数。

你可以对字符串进行3种操作：

1.插入一个字符

2.删除一个字符

3.修改一个字符。

字符串长度满足 $1 \le n \le 1000 \$ ，保证字符串中只出现小写英文字母。

示例1

输入

"nowcoder","new"

输出

说明

"nowcoder"=>"newcoder"(将'o'替换为'e')，修改操作1次
"nowcoder"=>"new"(删除"coder")，删除操作5次

示例2

输入

"intention","execution"

输出

说明

一种方案为:
因为2个长度都是9，后面的4个后缀的长度都为"tion"，于是从"inten"到"execu"逐个修改即可

示例3

输入

"now","nowcoder"

输出

算法知识视频讲解

Python3

Namely

class Solution:
    def editDistance(self , str1: str, str2: str) -> int:
        m, n = len(str1), len(str2)
        dp = [[0 for _ in range(n+1)] for _ in range(m+1)]
        for i in range(m+1):
            dp[i][0] = i
        for j in range(n+1):
            dp[0][j] = j
        for i in range(m):
            for j in range(n):
                if str1[i] == str2[j]:
                    dp[i+1][j+1] = dp[i][j]
                else:
                    dp[i+1][j+1] = min(dp[i][j+1], dp[i+1][j], dp[i][j]) + 1
        return dp[m][n]

发表于 2023-03-08 09:52:10 回复(0)

Python3

JianYue

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

发表于 2022-10-05 20:40:04 回复(0)