首页 > 试题广场 >

编辑距离

[编程题]编辑距离
  • 热度指数：14706 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
给定两个单词word1和word2，请计算将word1转换为word2至少需要多少步操作。
你可以对一个单词执行以下3种操作：
a）在单词中插入一个字符
b）删除单词中的一个字符
c）替换单词中的一个字符
示例1

输入

"b",""

输出

1
示例2

输入

"ab","bc"

输出

2
算法知识视频讲解
开通博客
头像 哈哈哈哈鹅
发表于 2021-11-17 19:30:26
可用二维数组i,j表示从word1的前i个字符到word2的前j个字符 dp[i][j]表示由word1的前i个字符转换为word2的前j个字符的最小编辑距离。 状态公式： 有两种情况： 1.当第i个字符和第j个字符相等时，那么从i到j的最小编辑距离只需要计算前i-1个字符到前j-1个字符的最小编 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 新时代——农民工
发表于 2023-03-13 20:34:36
import java.util.*; /** 编辑距离 * 给定两个单词word1和word2，请计算将word1转换为word2至少需要多少步操作。 * 你可以对一个单词执行以下3种操作： * a）在单词中插入一个字符 * b）删除单词中的一个字符 * c）替换单词中的一个字符 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 华科不平凡
发表于 2020-08-30 18:55:28
dp[i][j]表示由word1的前i个字符转换为word2的前j个字符的最小编辑距离。状态公式： 如果word1[i-1] = word2[j-1]，dp[i][j] = dp[i-1][j-1] 如果word1[i-1] != word2[j-1], dp[i][j] = min(dp[i-1 展开全文
去ta的博客 赞 (0) 回复(1) 收起
头像 牛客Yhq
发表于 2023-03-25 11:09:15
// 状态：F(i,j)-->word1的前i个字符变成word2的前j个字符 // 转移方程：通过一步变成F(i,j)的状态有三种： // F(i-1,j)删除word1第i个字符 // F(i,j-1)插入一个字符即word2的第j个字符 // 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 牛马ID
发表于 2022-03-26 09:29:45
动态规划思路 : 定义状态,f(i,j) 表示 word1 前 i 个字符(不包括 i) ,word2 前 j 个字符(不包括 j),转换最少的步骤! 确定状态转移方程(即迭代方向) f(i,j) = if(word1[i-1] != word2[j-1]) min(f(i-1,j- 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

动态规划
难度：
55条回答 26984浏览

热门推荐

通过挑战的用户

查看代码

相关试题

编辑距离

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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