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

本文涉及的产品
云解析DNS,个人版 1个月
公共DNS(含HTTPDNS解析),每月1000万次HTTP解析
全局流量管理 GTM,标准版 1个月
简介: 深入解析力扣161题:相隔为 1 的编辑距离(逐字符比较与动态规划详解)

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

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

在本篇文章中,我们将详细解读力扣第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 False
    
    for 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 False
    
    dp = [[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] = j
            elif j == 0:
                dp[i][j] = i
            elif 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  3
 a  1  0  1  2
 b  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”。
  1. 测试案例 2
  • 输入: s = "cab", t = "ad"
  • 输出: false
  • 解释: 无论进行哪种编辑操作,都不能将 s 转换为 t。
  1. 测试案例 3
  • 输入: s = "1203", t = "1213"
  • 输出: true
  • 解释: 可以通过替换字符 ‘0’ 为字符 ‘1’ 使得字符串 t 变为 “1213”。

总结

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

参考资料

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

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

❤️❤️关注公众号 数据分析螺丝钉 回复 学习资料 领取高价值免费学习资料❥(^_-)

欢迎关注微信公众号 数据分析螺丝钉

相关文章
|
7天前
|
算法 Python
算法不再难!Python分治法、贪心、动态规划实战解析,轻松应对各种算法挑战!
【7月更文挑战第8天】掌握Python算法三剑客:分治、贪心、动态规划。分治如归并排序,将大问题拆解递归解决;贪心策略在每步选最优解,如高效找零;动态规划利用子问题解,避免重复计算,解决最长公共子序列问题。实例展示,助你轻松驾驭算法!**
17 3
|
16天前
|
缓存
力扣每日一题 6/14 动态规划+数组
力扣每日一题 6/14 动态规划+数组
14 1
|
1天前
|
存储 SQL Python
`urllib.parse`模块是Python标准库`urllib`中的一个子模块,它提供了处理URL(统一资源定位符)的实用功能。这些功能包括解析URL、组合URL、转义URL中的特殊字符等。
`urllib.parse`模块是Python标准库`urllib`中的一个子模块,它提供了处理URL(统一资源定位符)的实用功能。这些功能包括解析URL、组合URL、转义URL中的特殊字符等。
5 0
|
12天前
|
索引
821.字符的最短距离-力扣(LeetCode)
821.字符的最短距离-力扣(LeetCode)
9 0
|
1月前
|
SQL 算法 大数据
深入解析力扣184题:部门工资最高的员工(子查询与窗口函数详解)
深入解析力扣184题:部门工资最高的员工(子查询与窗口函数详解)
|
16天前
|
算法 索引
力扣每日一题 6/28 动态规划/数组
力扣每日一题 6/28 动态规划/数组
14 0
|
16天前
|
存储
力扣每日一题 6/19 排序+动态规划
力扣每日一题 6/19 排序+动态规划
9 0
|
16天前
|
算法
力扣每日一题 6/16 字符串 + 随机一题 动态规划/数学
力扣每日一题 6/16 字符串 + 随机一题 动态规划/数学
11 0
|
16天前
|
算法
力扣经典150题解析之三十四:有效的数独
力扣经典150题解析之三十四:有效的数独
8 0
|
16天前
|
存储 算法 程序员
力扣经典150题第三十一题:无重复字符的最长子串
力扣经典150题第三十一题:无重复字符的最长子串
12 0

推荐镜像

更多