程序员面试金典 - 面试题 01.05. 一次编辑

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

  1. 两个字符串长度需要满足什么关系?
解决方案思路
  • 分析题目 , 只能有一次编辑 , 所以两个字符串长度的绝对值之差最多为 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]
原题链接: