深入解析力扣161题:相隔为 1 的编辑距离(逐字符比较与动态规划详解)

本文主要是介绍深入解析力扣161题:相隔为 1 的编辑距离(逐字符比较与动态规划详解),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

❤️❤️❤️ 欢迎来到我的博客。希望您能在这里找到既有价值又有趣的内容,和我一起探索、学习和成长。欢迎评论区畅所欲言、享受知识的乐趣!

  • 推荐:数据分析螺丝钉的首页 格物致知 终身学习 期待您的关注
    在这里插入图片描述

  • 导航

    • LeetCode解锁1000题: 打怪升级之旅:每题都包括3-5种算法,以及详细的代码实现,刷题面试跳槽必备
    • 漫画版算法详解:通过漫画的形式和动态GIF图片把复杂的算法每一步进行详细可视解读,看一遍就掌握
    • python源码解读:解读python的源代码与调用关系,快速提升代码质量
    • python数据分析可视化:企业实战案例:企业级数据分析案例与可视化,提升数据分析思维和可视化能力
    • 程序员必备的数学知识与应用:全面详细的介绍了工程师都必备的数学知识

期待与您一起探索技术、持续学习、一步步打怪升级 欢迎订阅本专栏❤️❤️

在本篇文章中,我们将详细解读力扣第161题“相隔为 1 的编辑距离”。通过学习本篇文章,读者将掌握如何判断两个字符串是否只有一个编辑操作的距离,并了解相关的复杂度分析。除了逐字符比较的方法,还将介绍其他解法。每种方法都将配以详细的解释和ASCII图解,以便于理解。

问题描述

力扣第161题“相隔为 1 的编辑距离”描述如下:

给定两个字符串 st,判断它们是否只有一个编辑操作的距离。编辑操作包括插入一个字符、删除一个字符或者替换一个字符。

示例 1:

输入: s = "ab", t = "acb"
输出: true
解释: 可以通过插入一个字符 'c' 使得字符串 t 变为 "abc"。

示例 2:

输入: s = "cab", t = "ad"
输出: false
解释: 无论进行哪种编辑操作,都不能将 s 转换为 t。

示例 3:

输入: s = "1203", t = "1213"
输出: true
解释: 可以通过替换字符 '0' 为字符 '1' 使得字符串 t 变为 "1213"。

解题思路

  1. 初步分析
    • 两个字符串之间只有一个编辑操作的距离,意味着我们可以通过一次插入、删除或替换一个字符将其中一个字符串转换为另一个字符串。
    • 可以通过比较字符串的长度来判断可能的编辑操作类型。

方法一:逐字符比较

  1. 步骤
    • 首先比较两个字符串的长度,判断可能的编辑操作类型。
    • 如果长度相同,则检查是否可以通过一次替换操作将一个字符串转换为另一个字符串。
    • 如果长度相差为1,则检查是否可以通过一次插入或删除操作将一个字符串转换为另一个字符串。
代码实现
def isOneEditDistance(s, t):m, n = len(s), len(t)# 确保 s 是较短的字符串if m > n:return isOneEditDistance(t, s)# 长度差大于1,则不可能只通过一次编辑操作完成转换if n - m > 1:return Falsefor i in range(m):if s[i] != t[i]:# 长度相同,则必须是一次替换操作if m == n:return s[i + 1:] == t[i + 1:]# 长度不同,则必须是一次插入操作else:return s[i:] == t[i + 1:]# 字符串末尾插入情况return m + 1 == n# 测试案例
print(isOneEditDistance("ab", "acb"))  # 输出: true
print(isOneEditDistance("cab", "ad"))  # 输出: false
print(isOneEditDistance("1203", "1213"))  # 输出: true
ASCII图解

假设输入字符串为 “ab” 和 “acb”,图解如下:

s = "ab"
t = "acb"逐字符比较:
s[0] == t[0] -> 'a' == 'a'
s[1] != t[1] -> 'b' != 'c'
检查 s[1:] == t[2:] -> "b" == "b"返回 true

方法二:动态规划

动态规划是一种更为通用的方法,虽然在这个问题中并不一定是最优解法,但它在处理更多编辑操作(如多次编辑操作)时非常有用。

  1. 步骤
    • 构建一个二维数组 dp,其中 dp[i][j] 表示字符串 s[0:i]t[0:j] 的编辑距离。
    • 初始化 dp 数组,对于空字符串的编辑操作初始化为其长度。
    • 填充 dp 数组,根据不同的编辑操作(插入、删除、替换)更新 dp 值。
    • 检查 dp 数组最后一行和最后一列的值,判断是否为1。
代码实现
def isOneEditDistanceDP(s, t):m, n = len(s), len(t)if abs(m - n) > 1:return Falsedp = [[0] * (n + 1) for _ in range(m + 1)]for i in range(m + 1):for j in range(n + 1):if i == 0:dp[i][j] = jelif j == 0:dp[i][j] = ielif s[i - 1] == t[j - 1]:dp[i][j] = dp[i - 1][j - 1]else:dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])return dp[m][n] == 1# 测试案例
print(isOneEditDistanceDP("ab", "acb"))  # 输出: true
print(isOneEditDistanceDP("cab", "ad"))  # 输出: false
print(isOneEditDistanceDP("1203", "1213"))  # 输出: true
ASCII图解

假设输入字符串为 “ab” 和 “acb”,图解如下:

s = "ab"
t = "acb"动态规划表格:''  a  c  b
''  0  1  2  3a  1  0  1  2b  2  1  1  1检查 dp[2][3] == 1
返回 true

复杂度分析

  • 时间复杂度
    • 逐字符比较法:O(n),其中 n 是较短字符串的长度。
    • 动态规划法:O(m * n),其中 m 和 n 分别是字符串 s 和 t 的长度。
  • 空间复杂度
    • 逐字符比较法:O(1),只使用了常数空间来存储计数变量和索引。
    • 动态规划法:O(m * n),需要额外的二维数组空间来存储 dp 值。

测试案例分析

  1. 测试案例 1

    • 输入: s = "ab", t = "acb"
    • 输出: true
    • 解释: 可以通过插入一个字符 ‘c’ 使得字符串 t 变为 “abc”。
  2. 测试案例 2

    • 输入: s = "cab", t = "ad"
    • 输出: false
    • 解释: 无论进行哪种编辑操作,都不能将 s 转换为 t。
  3. 测试案例 3

    • 输入: s = "1203", t = "1213"
    • 输出: true
    • 解释: 可以通过替换字符 ‘0’ 为字符 ‘1’ 使得字符串 t 变为 “1213”。

总结

本文详细解读了力扣第161题“相隔为 1 的编辑距离”,通过逐字符比较和动态规划两种方法,高效地解决了这一问题。希望读者通过本文的学习,能够在力扣刷题的过程中更加得心应手。

参考资料

  • 《算法导论》—— Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein
  • 力扣官方题解

🌹🌹如果觉得这篇文对你有帮助的话,记得一键三连关注、赞👍🏻、收藏是对作者最大的鼓励,非常感谢 ❥(^_-)

❤️❤️关注公众号 数据分析螺丝钉 回复 学习资料 领取高价值免费学习资料❥(^_-)
在这里插入图片描述

这篇关于深入解析力扣161题:相隔为 1 的编辑距离(逐字符比较与动态规划详解)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1001082

相关文章

Linux换行符的使用方法详解

《Linux换行符的使用方法详解》本文介绍了Linux中常用的换行符LF及其在文件中的表示,展示了如何使用sed命令替换换行符,并列举了与换行符处理相关的Linux命令,通过代码讲解的非常详细,需要的... 目录简介检测文件中的换行符使用 cat -A 查看换行符使用 od -c 检查字符换行符格式转换将

使用Jackson进行JSON生成与解析的新手指南

《使用Jackson进行JSON生成与解析的新手指南》这篇文章主要为大家详细介绍了如何使用Jackson进行JSON生成与解析处理,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录1. 核心依赖2. 基础用法2.1 对象转 jsON(序列化)2.2 JSON 转对象(反序列化)3.

Springboot @Autowired和@Resource的区别解析

《Springboot@Autowired和@Resource的区别解析》@Resource是JDK提供的注解,只是Spring在实现上提供了这个注解的功能支持,本文给大家介绍Springboot@... 目录【一】定义【1】@Autowired【2】@Resource【二】区别【1】包含的属性不同【2】@

详解C#如何提取PDF文档中的图片

《详解C#如何提取PDF文档中的图片》提取图片可以将这些图像资源进行单独保存,方便后续在不同的项目中使用,下面我们就来看看如何使用C#通过代码从PDF文档中提取图片吧... 当 PDF 文件中包含有价值的图片,如艺术画作、设计素材、报告图表等,提取图片可以将这些图像资源进行单独保存,方便后续在不同的项目中使

Android中Dialog的使用详解

《Android中Dialog的使用详解》Dialog(对话框)是Android中常用的UI组件,用于临时显示重要信息或获取用户输入,本文给大家介绍Android中Dialog的使用,感兴趣的朋友一起... 目录android中Dialog的使用详解1. 基本Dialog类型1.1 AlertDialog(

C#数据结构之字符串(string)详解

《C#数据结构之字符串(string)详解》:本文主要介绍C#数据结构之字符串(string),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录转义字符序列字符串的创建字符串的声明null字符串与空字符串重复单字符字符串的构造字符串的属性和常用方法属性常用方法总结摘

C#如何动态创建Label,及动态label事件

《C#如何动态创建Label,及动态label事件》:本文主要介绍C#如何动态创建Label,及动态label事件,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录C#如何动态创建Label,及动态label事件第一点:switch中的生成我们的label事件接着,

SpringCloud动态配置注解@RefreshScope与@Component的深度解析

《SpringCloud动态配置注解@RefreshScope与@Component的深度解析》在现代微服务架构中,动态配置管理是一个关键需求,本文将为大家介绍SpringCloud中相关的注解@Re... 目录引言1. @RefreshScope 的作用与原理1.1 什么是 @RefreshScope1.

Java并发编程必备之Synchronized关键字深入解析

《Java并发编程必备之Synchronized关键字深入解析》本文我们深入探索了Java中的Synchronized关键字,包括其互斥性和可重入性的特性,文章详细介绍了Synchronized的三种... 目录一、前言二、Synchronized关键字2.1 Synchronized的特性1. 互斥2.

MyBatis 动态 SQL 优化之标签的实战与技巧(常见用法)

《MyBatis动态SQL优化之标签的实战与技巧(常见用法)》本文通过详细的示例和实际应用场景,介绍了如何有效利用这些标签来优化MyBatis配置,提升开发效率,确保SQL的高效执行和安全性,感... 目录动态SQL详解一、动态SQL的核心概念1.1 什么是动态SQL?1.2 动态SQL的优点1.3 动态S