牛客网 HJ52 计算字符串的编辑距离

牛客网 HJ52 计算字符串的编辑距离题目链接https://www.nowcoder.com/practice/3959837097c7413a961a135d7104c314一、原题完整陈述题目描述Levenshtein距离编辑距离把字符串s变换成字符串t最少的单字符操作次数。允许3种操作每一次算1步插入一个字符删除一个字符替换一个字符求两个字符串的编辑距离。输入描述第一行字符串s小写字母长度1~1000第二行字符串t小写字母长度1~1000输出描述输出整数s和t的编辑距离样例输入abcdefg abcdef样例输出1解释s删掉末尾g或者t末尾插入g只需要1次操作。另一个经典例子kitten→sitting编辑距离3二、费曼学习法拆解破解思路讲给小白翻译成大白话给你两个单词只能增、删、改单个字母问最少要改多少次才能把第一个单词变成第二个单词。核心动态规划拆成子问题只看两个字符串前面一小段前缀算出这小段最少操作数一步步从小推到大。DP数组定义dp[i][j]s的前i个字符变成t的前j个字符最少操作次数注意s[i-1]才是第i个字符因为字符串下标从0开始dp表从0开始。边界条件最简单的子问题dp[i][0]t是空串。s前i个字符全部删掉需要i次删除。dp[i][0]idp[0][j]s是空串。空串变成t前j个字符需要j次插入。dp[0][j]j状态转移核心逻辑当处理s[i-1]和t[j-1]如果两个字符相等不用任何操作直接继承前面结果dp[i][j]dp[i−1][j−1]dp[i][j] dp[i-1][j-1]dp[i][j]dp[i−1][j−1]如果两个字符不相等有3种可选操作取最小操作数1当前这一步删除s当前字符dp[i-1][j]1在s里插入t当前字符dp[i][j-1]1把s当前字符替换成t当前字符dp[i-1][j-1]1dp[i][j]min⁡(dp[i−1][j],dp[i][j−1],dp[i−1][j−1])1dp[i][j]\min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])1dp[i][j]min(dp[i−1][j],dp[i][j−1],dp[i−1][j−1])1手动模拟小样例sabcdefgtabcdefm7n6dp[7][6]就是答案1。前面abcdef完全匹配最后多一个g删除一次即可。坑点提醒dp表的下标和字符串下标错位dp[i][j]对应s[0:i]、t[0:j]字符相等的时候不加1很多新手在这里多加1导致答案错误。字符串最大长度1000二维数组(1001 × 1001)Python完全可以承受。解法分类解法1二维DP填表机考首选直观好写下面代码解法2一维空间优化DP空间压缩面试加分减少内存解法3朴素递归重复计算长字符串会超时不推荐机考三、二维DP Python完整代码 逐行详细注释# HJ52 计算字符串编辑距离 Levenshtein距离# 动态规划二维DP版本牛客华为机考标准写法if__name____main__:# 读取第一行字符串ssinput().strip()# 读取第二行字符串ttinput().strip()# m是s的长度n是t的长度mlen(s)nlen(t)# 创建dp二维数组# dp[i][j]代表 s前i个字符 → t前j个字符的最少操作次数# 数组大小 (m1)行(n1)列全部初始化为0dp[[0]*(n1)for_inrange(m1)]# 初始化边界1t是空串 dp[i][0]# s前i个字符变成空串需要删除i次foriinrange(m1):dp[i][0]i# 初始化边界2s是空串 dp[0][j]# 空串变成t前j个字符需要插入j次forjinrange(n1):dp[0][j]j# 双重循环填表从小到大计算子问题# i遍历s的前i个字符从1到mforiinrange(1,m1):# j遍历t的前j个字符从1到nforjinrange(1,n1):# s的第i个字符s[i-1]t的第j个字符t[j-1]ifs[i-1]t[j-1]:# 字符相等不需要操作继承左上角的值dp[i][j]dp[i-1][j-1]else:# 字符不等三种方案选最小再1本次操作# 方案1删除s当前字符 dp[i-1][j]# 方案2向s插入t当前字符 dp[i][j-1]# 方案3替换当前字符 dp[i-1][j-1]dp[i][j]min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])1# dp[m][n]就是s全部字符转t全部字符的最小操作次数print(dp[m][n])测试样例输入abcdefg abcdef输出1四、空间压缩一维DP版本拓展逐行注释二维dp会占用 m*n空间一维只保留上一行空间复杂度 O(min(m,n))# HJ52 编辑距离 一维空间优化版本if__name____main__:sinput().strip()tinput().strip()# 保证t是短字符串减少数组长度iflen(s)len(t):s,tt,s mlen(s)nlen(t)# dp数组只保存上一行数据长度n1dplist(range(n1))foriinrange(1,m1):# prev保存左上角dp[i-1][j-1]的值初始是dp[i-1][0]prevdp[0]# 当前行第0列s前i字符转空串删除i次dp[0]iforjinrange(1,n1):# 暂存原来的dp[j]也就是下一轮的左上角值tempdp[j]ifs[i-1]t[j-1]:dp[j]prevelse:dp[j]min(dp[j],dp[j-1],prev)1# 更新prev保存左上角旧值prevtempprint(dp[n])五、时间空间复杂度分析二维DP版本时间复杂度O(m×n)\boldsymbol{O(m\times n)}O(m×n)两层循环每个单元格常数运算m,n是两个字符串长度空间复杂度O(m×n)\boldsymbol{O(m\times n)}O(m×n)二维数组 (m1)*(n1)一维优化版本时间复杂度O(m×n)\boldsymbol{O(m\times n)}O(m×n)时间不变空间复杂度O(min⁡(m,n))\boldsymbol{O(\min(m,n))}O(min(m,n))只保留一行数组朴素递归版本不推荐时间指数O(2max⁡(m,n))O(2^{\max(m,n)})O(2max(m,n))大量重复子问题长字符串超时。六、真实应用场景举例场景1输入法拼写纠错最经典用户输入错单词比如把helo打成hello。计算词典里所有单词和用户输入的编辑距离选出距离最小的词给出“你是不是想打hello”。搜索引擎“你是不是要搜xxx”底层就是编辑距离。场景2DNA/基因序列比对生物信息DNA是A/T/C/G字符串比较两段基因序列。插入、删除、突变对应基因变异编辑距离衡量物种基因相似度。场景3文档diff工具git diff文件对比git比较两个版本文件差异底层思想就是编辑距离算出最少增删改动。场景4数据库模糊匹配、数据清洗客户名字录入有笔误比如ZhangSan写成ZhangSanN计算编辑距离做重复数据去重。场景5OCR文字识别后校正图片识别文字经常识别错个别字母用编辑距离匹配字典修正识别结果。场景6AI文本评估大模型生成回答和标准答案做对比用编辑距离量化文本差异。七、费曼复盘总结HJ52编辑距离是字符串DP标杆题。核心思想拆前缀子问题dp[i][j]表示两个前缀之间最少操作。三种操作对应dp三个来源字符相等不用加操作步数。关键点边界空串的插入/删除次数字符相等直接继承左上角不等取三个方向最小值1二维DP直观一维DP可以压缩空间。知识点清单动态规划、二维DP、字符串DP、子问题最优子结构。拓展如果你想要我可以写记忆化递归版本代码输出每一步具体的编辑操作回溯dp表打印怎么增删改对比 LCS最长公共子序列 和编辑距离的数学关系。