面试题 01.05. 一次编辑
难度中等142收藏分享切换为英文接收动态反馈
字符串有三种编辑操作:插入一个字符、删除一个字符或者替换一个字符。 给定两个字符串，编写一个函数判定它们是否只需要一次(或者零次)编辑。
示例 1:
输入:
first = "pale"
second = "ple"
输出: True
示例 2:
输入:
first = "pales"
second = "pal"
输出: False
通过次数47,199提交次数142,718
解题思路：
如果两个字符串符合要求，那么他的前缀和 and 后缀和应该是相等的。
Python代码：
class Solution: def oneEditAway(self, first: str, second: str) -> bool: p1 , p2 , q1 , q2 = 0 , 0 , len(first)-1 , len(second)-1 while p1<=q1 and p2<=q2: if first[p1]==second[p2]: p1 += 1 p2 += 1 continue elif first[q1]==second[q2]: q1 -= 1 q2 -= 1 else: break return q1-p1 + q2-p2<=0 and abs(p1-p2)<=1 and abs(q1-q2)<=1
C++代码：
class Solution { public: bool oneEditAway(string first, string second) { int p1 = 0 , p2 = 0; int q1 = first.size()-1 , q2 = second.size()-1; while (p1<=q1 && p2<=q2) { if (first[p1]==second[p2]){ p1++; p2++; continue; } else if (first[q1] == second[q2]){ q1--; q2--; } else break; } return q1-p1 + q2-p2 <=0 && abs(p2-p1)<=1 && abs(q2-q1)<=1; } };
python的快速解法：
class Solution: def oneEditAway(self, first: str, second: str) -> bool: m , n = len(first) , len(second) if m-n>1:return False if m<n:return self.oneEditAway(second , first) for i , (x , y) in enumerate(zip(first , second)): if x!=y: return first[i+1:]==second[i+1:] if m==n else first[i+1:]==second[i:] return True
