当前位置: 首页 > news >正文

72. 编辑距离

问题

给你两个单词 word1 和 word2, 请返回将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作:

插入一个字符
删除一个字符
替换一个字符

示例 1:
输入:word1 = "horse", word2 = "ros"
输出:3
解释:
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

分析

f[i][j]表示s1的前i个字符变成s2的前j个字符最少操作数,以s1视角,添加:f[i][j] = f[i][j-1]+1;删除:f[i][j] = f[i-1][j]+1;替换:f[i][j] = f[i-1][j-1] + 1。如果当前比较的两个字符相等,s1[i-1] == s2[j-1],有 dp[i][j] = dp[i-1][j-1].

代码

class Solution {
public:string s1, s2;int n1, n2;static const int N = 5e2+10;int f[N][N]; // f[i][j]表示s1的前i个字符变成s2的前j个字符最少操作数int minDistance(string word1, string word2) {this->s1 = word1, this->s2 = word2;n1 = word1.size(); n2 = word2.size();for (int i = 0; i <= n1; i++) {f[i][0] = i; // s1的前i个字符变为空串}for (int i = 0; i <= n2; i++) {f[0][i] = i;}// 在s1 insert相当于在s2 deletefor (int i = 1; i <= n1; i++) {for (int j = 1; j <= n2; j++) {if (s1[i-1] != s2[j-1]) {f[i][j] = min(min(f[i-1][j]+1, f[i][j-1]+1), f[i-1][j-1]+1);} else {f[i][j] = f[i-1][j-1];}}}return f[n1][n2];}
};
http://www.hskmm.com/?act=detail&tid=22673

相关文章:

  • PlantUML 完整教程:从入门到精通
  • 你妈的
  • test6
  • test7
  • 学习java的第三天
  • vscode github 推送失败
  • 信奥大联赛周赛(提高组)#2515-S 赛后盘点
  • 虚拟机仅主机模式下使用ssh远程连接Linux(EHEL8)连接慢,需要等待30秒以上
  • VLC Player插件和自动激活
  • 第七天
  • logback.xml 常用配置详解 - Higurashi
  • MySQL COUNT(*)性能对比:MyISAM为何比InnoDB快?全面解析与优化方案
  • 2025.10.1总结
  • 子结构判断
  • 使用 Go 进行验证码识别
  • 使用 Rust 进行验证码识别
  • 使用 Swift 进行验证码识别
  • torchtext与torch版本对应关系
  • Python错题集
  • 火狐浏览器新页覆盖旧页解决方法
  • msi主板,windows11,mbr转gpt后,提示0xc000000e1,无法进入系统
  • MAUI下热重载不生效
  • AdGuard广告拦截器APP v4.11.63 / 4.13.7 Nightly 修改版
  • 在疼痛中锚定前路
  • Chrome在Android上Speedometer性能翻倍的技术揭秘
  • 《电路基础》第四章学习笔记
  • 题解:AT_arc184_d [ARC184D] Erase Balls 2D
  • US$39 PowerBox for KTM JTAG for Hitachi
  • 最小二乘问题详解2:线性最小二乘求解
  • OpenAI炸场!Sora 2正式发布,它不只是个视频模型,更是一个社交宇宙!