中山企业网站设计,高明网站设计制作,大连企业做网站公司排名,html网页导航栏代码❤️❤️❤️ 欢迎来到我的博客。希望您能在这里找到既有价值又有趣的内容#xff0c;和我一起探索、学习和成长。欢迎评论区畅所欲言、享受知识的乐趣#xff01; 推荐#xff1a;数据分析螺丝钉的首页 格物致知 终身学习 期待您的关注 导航#xff1a; LeetCode解锁100… ❤️❤️❤️ 欢迎来到我的博客。希望您能在这里找到既有价值又有趣的内容和我一起探索、学习和成长。欢迎评论区畅所欲言、享受知识的乐趣 推荐数据分析螺丝钉的首页 格物致知 终身学习 期待您的关注 导航 LeetCode解锁1000题: 打怪升级之旅每题都包括3-5种算法以及详细的代码实现刷题面试跳槽必备漫画版算法详解通过漫画的形式和动态GIF图片把复杂的算法每一步进行详细可视解读看一遍就掌握python源码解读解读python的源代码与调用关系快速提升代码质量python数据分析可视化企业实战案例企业级数据分析案例与可视化提升数据分析思维和可视化能力程序员必备的数学知识与应用全面详细的介绍了工程师都必备的数学知识 期待与您一起探索技术、持续学习、一步步打怪升级 欢迎订阅本专栏❤️❤️ 在本篇文章中我们将详细解读力扣第161题“相隔为 1 的编辑距离”。通过学习本篇文章读者将掌握如何判断两个字符串是否只有一个编辑操作的距离并了解相关的复杂度分析。除了逐字符比较的方法还将介绍其他解法。每种方法都将配以详细的解释和ASCII图解以便于理解。
问题描述
力扣第161题“相隔为 1 的编辑距离”描述如下 给定两个字符串 s 和 t判断它们是否只有一个编辑操作的距离。编辑操作包括插入一个字符、删除一个字符或者替换一个字符。 示例 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则检查是否可以通过一次插入或删除操作将一个字符串转换为另一个字符串。
代码实现
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)) # 输出: trueASCII图解
假设输入字符串为 “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方法二动态规划
动态规划是一种更为通用的方法虽然在这个问题中并不一定是最优解法但它在处理更多编辑操作如多次编辑操作时非常有用。
步骤 构建一个二维数组 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)) # 输出: trueASCII图解
假设输入字符串为 “ab” 和 “acb”图解如下
s ab
t acb动态规划表格: a c b0 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 输入: 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”。
总结
本文详细解读了力扣第161题“相隔为 1 的编辑距离”通过逐字符比较和动态规划两种方法高效地解决了这一问题。希望读者通过本文的学习能够在力扣刷题的过程中更加得心应手。
参考资料
《算法导论》—— Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein力扣官方题解 如果觉得这篇文对你有帮助的话记得一键三连关注、赞、收藏是对作者最大的鼓励非常感谢 ❥(^_-) ❤️❤️关注公众号 数据分析螺丝钉 回复 学习资料 领取高价值免费学习资料❥(^_-)
