程序员面试金典 - 面试题 01.05. 一次编辑
题目难度: 中等
【程序员面试金典 - 面试题 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]原题链接:
- 28岁程序员狂赚上亿,宣布退休:有钱一时爽,一直有钱一直爽
- 用尽全身力气不想加班的机器人,这大概是程序员最后的倔强,哈哈
- Java函数式编码结构-好程序员
- 又是一年1024,程序员:我写的算法不足以控制人类
- 阿里员工哀叹:公务员真好,每一样都完爆程序员,网友:想得真美
- 一个普通本科的安卓程序员如何才能进腾讯,阿里,字节这些大厂?
- 阿里铁军原主帅俞朝翎:阿里面试中的“望闻问切”法
- 印度程序员眼中的中国科技如何?这个观点很刻薄,但却很真实
- 从高级程序员-资深程序员-技术总监,我都为你整理好了学习路径
- IT程序员常去的论坛、社区、网站