程序员面试金典 - 面试题 01.05. 一次编辑题目难度:中等原题链接[1]今天继续更新

题目难度: 中等
【程序员面试金典 - 面试题 01.05. 一次编辑】原题链接[1]
今天继续更新程序员面试金典系列, 大家在公众号算法精选里回复面试金典就能看到该系列当前连载的所有文章了, 记得关注哦~
题目描述字符串有三种编辑操作:插入一个字符、删除一个字符或者替换一个字符。给定两个字符串，编写一个函数判定它们是否只需要一次(或者零次)编辑。
示例 1:输入: first = "pale" second = "ple" 输出: True
示例 2:输入: first = "pales" second = "pal" 输出: False
题目思考

两个字符串长度需要满足什么关系？

解决方案思路

分析题目，只能有一次编辑，所以两个字符串长度的绝对值之差最多为 1
所以我们要先判断长度是否满足要求，满足的话使用双指针 + 一个 bool 变量 edited（标记是否已经编辑过）来遍历，遇到不匹配的字符时：如果 edited 是 true ，直接返回 false ，因为已经编辑过一次了；如果 edited 是 false ，则根据长度关系决定是哪种编辑操作，并移动对应的下标，然后更新 edited 为 true 。

复杂度

时间复杂度 O(N): 需要遍历两个字符串一遍
空间复杂度 O(1): 只使用了几个变量

代码

class Solution:def oneEditAway(self, first: str, second: str) -> bool:# 判断长度差+双指针, 分三种情况if abs(len(first) - len(second)) > 1:return Falsei, j = 0, 0edited = Falsewhile i < len(first) and j < len(second):if first[i] == second[j]:i += 1j += 1else:if edited:return Falseif len(first) < len(second):# first需要插入一个字符, 所以second下标后移一位, 代表插入字符和second[j]匹配j += 1elif len(first) > len(second):# first需要删除一个字符, 所以first下标后移一位i += 1else:# first需要改变当前字符first[i]=>second[j], 所以两个下标都后移一位i += 1j += 1edited = Truereturn True

参考资料[1]
原题链接: