深入解析力扣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

相关文章

MySQL 中的 JSON 查询案例详解

《MySQL中的JSON查询案例详解》:本文主要介绍MySQL的JSON查询的相关知识,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录mysql 的 jsON 路径格式基本结构路径组件详解特殊语法元素实际示例简单路径复杂路径简写操作符注意MySQL 的 J

Golang HashMap实现原理解析

《GolangHashMap实现原理解析》HashMap是一种基于哈希表实现的键值对存储结构,它通过哈希函数将键映射到数组的索引位置,支持高效的插入、查找和删除操作,:本文主要介绍GolangH... 目录HashMap是一种基于哈希表实现的键值对存储结构,它通过哈希函数将键映射到数组的索引位置,支持

SpringBoot基于配置实现短信服务策略的动态切换

《SpringBoot基于配置实现短信服务策略的动态切换》这篇文章主要为大家详细介绍了SpringBoot在接入多个短信服务商(如阿里云、腾讯云、华为云)后,如何根据配置或环境切换使用不同的服务商,需... 目录目标功能示例配置(application.yml)配置类绑定短信发送策略接口示例:阿里云 & 腾

Python ZIP文件操作技巧详解

《PythonZIP文件操作技巧详解》在数据处理和系统开发中,ZIP文件操作是开发者必须掌握的核心技能,Python标准库提供的zipfile模块以简洁的API和跨平台特性,成为处理ZIP文件的首选... 目录一、ZIP文件操作基础三板斧1.1 创建压缩包1.2 解压操作1.3 文件遍历与信息获取二、进阶技

一文详解Java异常处理你都了解哪些知识

《一文详解Java异常处理你都了解哪些知识》:本文主要介绍Java异常处理的相关资料,包括异常的分类、捕获和处理异常的语法、常见的异常类型以及自定义异常的实现,文中通过代码介绍的非常详细,需要的朋... 目录前言一、什么是异常二、异常的分类2.1 受检异常2.2 非受检异常三、异常处理的语法3.1 try-

Java中的@SneakyThrows注解用法详解

《Java中的@SneakyThrows注解用法详解》:本文主要介绍Java中的@SneakyThrows注解用法的相关资料,Lombok的@SneakyThrows注解简化了Java方法中的异常... 目录前言一、@SneakyThrows 简介1.1 什么是 Lombok?二、@SneakyThrows

Java中字符串转时间与时间转字符串的操作详解

《Java中字符串转时间与时间转字符串的操作详解》Java的java.time包提供了强大的日期和时间处理功能,通过DateTimeFormatter可以轻松地在日期时间对象和字符串之间进行转换,下面... 目录一、字符串转时间(一)使用预定义格式(二)自定义格式二、时间转字符串(一)使用预定义格式(二)自

Redis Pipeline(管道) 详解

《RedisPipeline(管道)详解》Pipeline管道是Redis提供的一种批量执行命令的机制,通过将多个命令一次性发送到服务器并统一接收响应,减少网络往返次数(RTT),显著提升执行效率... 目录Redis Pipeline 详解1. Pipeline 的核心概念2. 工作原理与性能提升3. 核

Python正则表达式语法及re模块中的常用函数详解

《Python正则表达式语法及re模块中的常用函数详解》这篇文章主要给大家介绍了关于Python正则表达式语法及re模块中常用函数的相关资料,正则表达式是一种强大的字符串处理工具,可以用于匹配、切分、... 目录概念、作用和步骤语法re模块中的常用函数总结 概念、作用和步骤概念: 本身也是一个字符串,其中

Python使用getopt处理命令行参数示例解析(最佳实践)

《Python使用getopt处理命令行参数示例解析(最佳实践)》getopt模块是Python标准库中一个简单但强大的命令行参数处理工具,它特别适合那些需要快速实现基本命令行参数解析的场景,或者需要... 目录为什么需要处理命令行参数?getopt模块基础实际应用示例与其他参数处理方式的比较常见问http