首页 > 试题广场 >

编辑距离(一)

[编程题]编辑距离(一)
  • 热度指数：23778 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定两个字符串 str1 和 str2 ，请你算出将 str1 转为 str2 的最少操作数。
你可以对字符串进行3种操作：
1.插入一个字符
2.删除一个字符
3.修改一个字符。

字符串长度满足 ，保证字符串中只出现小写英文字母。
示例1

输入

"nowcoder","new"

输出

6

说明

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

输入

"intention","execution"

输出

5

说明

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

输入

"now","nowcoder"

输出

5
算法知识视频讲解
开通博客
头像 牛客题解官
发表于 2022-04-22 12:50:25
精华题解 题目主要信息: 给定两个长度可能不同的字符串，可以对第一个字符串增删改字符 求增删改的最少次数，让第一个字符串变成第二个字符串 字符串中只出现大小写字母 举一反三： 学习完本题的思路你可以解决如下题目： BM65 最长公共子序列(二) BM66.最长公共子串 BM71.最长上升子序列(一) BM 展开全文
去ta的博客 赞 (21) 回复(3) 收起
头像 godhands
发表于 2022-01-10 19:52:54
描述 题目描述 首先给我们了两个字符串，我们又三种操作分别是增删改，现在询问我们最少的操作次数，让两个字符串相同 样例解释 给我们样例 "nawcoder","nowcoder" 这里我们只需要把a改成oa改成oa改成o就可以得到第二个字符串，所以操作数是111 所以我们的输出是 1 对三种情况 展开全文
去ta的博客 赞 (5) 回复(0) 收起
头像 摸鱼学大师
发表于 2022-02-18 15:17:59
题目主要信息: 给定两个长度可能不同的字符串，可以对第一个字符串增删改字符 求增删改的最少次数，让第一个字符串变成第二个字符串 字符串中只出现大小写字母 具体思路: 把第一个字符串变成第二个字符串，我们需要逐个将第一个字符串的子串最少操作下变成第二个字符串，这就涉及了第一个字符串增加长度，状态转 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 奇怪的小黄狗
发表于 2022-02-28 15:23:29
public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param str1 string字符串 * @param str2 string字符串 * @return 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 勇敢牛牛生活灿烂
发表于 2022-09-19 16:23:27
# # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # #  # @param str1 string字符串  # @param str2 string字符串  #&nb 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 夕木月
发表于 2022-07-30 11:13:03
//时间复杂度为O（n*m），空间复杂度为O（n*m） int Min(int a,int b) {     if(a < b)         return a;     return b; } int edi 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 菜鸡孙连城
发表于 2022-03-25 21:08:37
看了题解原来这道题这么简单😱 下面我就要抄题解了 dp[i][j]dp[i][j]dp[i][j]表示为从str1str_1str1​的前iii位变化为str2str_2str2​的前jjj位需要的次数 str1[i]==str2[j]=>dp[i][j]=dp[i−1][j−1]str1[ 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 代码界的小白
发表于 2022-01-04 23:24:29
题目主要信息 1、给两个字符串str1，str2 2、每个字符串可以通过替换、增添、删除来进行修改，每次修改需要1次编辑距离 3、求最小编辑距离使得两个字符串相等 方法一:字符串比较 具体方法 编辑距离是一类非常经典的动态规划的题目。 我们使用dp[i][j]表示字符串A的前i个字符与字符串B的前j 展开全文
去ta的博客 赞 (1) 回复(2) 收起
头像 CroMarmot
发表于 2022-01-03 08:40:22
题意 字符串A最少需要多少次, 插入/删除/修改 能变成字符串B 限制,两个字符串长度均不超过500500500 方法 递推+状态 设计状态 dp[i][j] 表示,地一个字符串的前i个最少操作dp[i][j]次能变成第二个字符串前j 那么有状态转移 A[i]=B[j]时,对应位置字符相等,直接匹配 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 牛客281174060号
发表于 2022-04-13 11:58:00
有点难，详细的写在这里面了。 # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param str1 string字符串 # @param str2 string字符串 # @return int整型 # class Solution: d 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 勤奋的猫
发表于 2022-05-16 12:25:19
import java.util.*; public class Solution {     /**      * 代码中的类名、方法名、参数名已经指定， 展开全文
去ta的博客 赞 (1) 回复(0) 收起

问题信息

动态规划 字符串
难度：
40条回答 3718浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号