编辑距离(二)

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

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

给定两个字符串str1和str2，再给定三个整数ic，dc和rc，分别代表插入、删除和替换一个字符的代价，请输出将str1编辑成str2的最小代价。

数据范围： $0 \le |str1|,|str2| \le 5000$ ， $0\le ic,dc,rc \le 10000\$

要求：空间复杂度 $O(n)$ ，时间复杂度 $O(nlogn)$

示例1

输入

"abc","adc",5,3,2

输出

示例2

输入

"abc","adc",5,3,100

输出

备注:

算法知识视频讲解

漫漫云天自翱翔

发表于 2021-07-18 20:47:12

精华题解题解一：动态规划动态转移方程分析图示：复杂度分析：时间复杂度：O(MN) 空间复杂度：O(MN) 实现如下: class Solution { public: /** * min edit cost * @param st 展开全文

蒙牛麦片

发表于 2021-07-22 15:23:21

精华题解最小编辑代价题意分析：题解一（动态规划）：最优子结构：设输入序列为和，长度分别为m和n。假设为两个序列和在位置和位置的最短编辑数。如果两个序列的最后一个字符相等（或)，则如果两个序列的最后一个字符不相等()，则有三种选择：取三种选择最小操作数如有序列“AGAB” 和“GXAYB”。它们展开全文

LaN666

发表于 2021-07-19 01:43:17

精华题解动态规划dp函数 + 记忆数组算法思路先定义状态，匹配与不匹配两种。当不匹配时，有三种选择: 插入，删除，替换。dp(i, j)为str1[0...i]和str2[0..j]字符串为了匹配做出的代价。对于给定的字符串str1，str2，从右到左，即自顶向下进行匹配。会出现两种情况：当前字符匹展开全文

下一次什么时候可以修改昵称

发表于 2020-10-28 22:24:25

原题插入删除替换代价都是1 算法 1.动态规划：dp[i][j]表示word1的前i个字符编辑成word2的前j个字符需要的最小操作数 2.初始状态：dp[i][0] = i，i次删除；dp[0][i] = i，i次插入 3.过渡公式：当i字符等于j字符时：dp[i][j] = dp[i-1] 展开全文

有理想的咕咕

发表于 2021-01-07 21:01:07

最小编辑代价：给定两个字符串str1和str2，再给定三个整数ic，dc和rc，分别代表插入、删除和替换一个字符的代价，请输出将str1编辑成str2的最小代价。较难的动态规划题目(主要要着眼于三个基本操作带来的操作)：如果选择将str1的前i个字符转换为str2的前j个字符则需要分类讨论-& 展开全文

人定胜天~

发表于 2021-02-02 16:50:05

参考链接：https://leetcode-cn.com/problems/edit-distance/solution/bian-ji-ju-chi-by-leetcode-solution/我们可以对任意一个单词进行三种操作：在单词 A 中插入一个字符；在单词 A 中插入一个字符；修改单词 A 展开全文