首页 > 试题广场 >

字符串最小变换次数

[编程题]字符串最小变换次数
  • 热度指数：3204 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
给定两个字符串，已知可以使用三种方式进行变换
1. 插入一个字符
2. 删除一个字符
3. 更改一个字符
请设计一个算法，找到两个字符串之间的经历几次最小变换，可以字符串1转换成字符串2

数据范围：输入字符串的长度满足

输入描述:
输入两个字符串


输出描述:
最小变换次数
示例1

输入

hello
helle

输出

1
算法知识视频讲解
开通博客
头像 mihotel
发表于 2021-07-11 16:29:23
本题为计算字符串的编辑距离 设两个字符串s1, s2长度分别为m, n， f(m, n)为将s1变换为s2的最小变换次数。 考虑s1的第m个字符s1[m-1]，s2的第n个字符s2[n-1]（下标从0开始），有两种情况： s1[m-1] == s2[n-1]则最小变换次数为将s1的前m-1个字符变 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 必不可能秃头
发表于 2022-03-15 21:00:57
import java.util.*; public class Main{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); String str1 = 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 重生之我要当分子
发表于 2024-12-31 01:27:11
解题思路 状态定义： dp[i][j] 表示将字符串1的前i个字符转换成字符串2的前j个字符所需的最小操作次数 状态转移： 如果当前字符相同：dp[i][j] = dp[i-1][j-1] 如果当前字符不同，取三种操作的最小值： 插入：dp[i][j-1] + 1 删除：dp[i-1 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

C++工程师 iOS工程师 安卓工程师 快手 运维工程师 字符串 前端工程师 算法工程师 测试工程师 PHP工程师 动态规划 2019 Java工程师
上传者：小小
难度：
23条回答 10940浏览

热门推荐

通过挑战的用户

查看代码

相关试题

字符串最小变换次数

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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