难度: Medium
字符串有三种编辑操作:插入一个英文字符、删除一个英文字符或者替换一个英文字符。 给定两个字符串，编写一个函数判定它们是否只需要一次(或者零次)编辑。
示例 1:
输入: first = "pale" second = "ple" 输出: True
示例 2:
输入: first = "pales" second = "pal" 输出: False
Submission
运行时间: 19 ms
内存: 15.9 MB
class Solution:
def oneEditAway(self, first: str, second: str) -> bool:
lf, ls = len(first), len(second)
if lf > ls:
return self.oneEditAway(second, first)
if ls - lf > 1:
return False
if lf == ls:
count = 0
for i in range(lf):
if first[i] != second[i]:
count += 1
return count <= 1
i, ofs = 0, 0
while i < lf:
if first[i] != second[i + ofs]:
ofs += 1
if ofs > 1:
return False
else:
i += 1
return True
Explain
该题解首先通过比较两个字符串的长度来确定较短和较长的字符串，并保证后续操作总是在长度小的字符串上进行。如果两个字符串的长度差超过1，则直接返回False，因为无法通过一次操作使二者相同。接着，根据两个字符串长度是否相等分别处理：如果长度相等，则通过比较每个对应位置的字符，统计不同字符的数量是否超过1；如果长度不相等（此时长度差为1），则通过一个偏移量ofs来比对较短字符串中的每个字符是否与较长字符串中的对应位置匹配，一旦发现不匹配，则增加偏移量，并检查是否超过1次编辑的机会。
时间复杂度: O(n)
空间复杂度: O(1)
class Solution:
def oneEditAway(self, first: str, second: str) -> bool:
lf, ls = len(first), len(second)
# 确保处理时第一个字符串总是最短的
if lf > ls:
return self.oneEditAway(second, first)
# 如果长度差大于1，不可能通过一次编辑达成目标
if ls - lf > 1:
return False
# 如果长度相等，检查可以替换的字符数
if lf == ls:
count = 0
for i in range(lf):
if first[i] != second[i]:
count += 1
return count <= 1
# 处理插入或删除的情况
i, ofs = 0, 0
while i < lf:
if first[i] != second[i + ofs]:
ofs += 1
if ofs > 1:
return False
else:
i += 1
return True
Explore
在处理长度不相等的情况下，我们的目标是通过一次插入或删除操作来使两个字符串相等。这里的关键是使用一个单一的偏移量`ofs`来模拟插入或删除操作的效果。当我们在比较过程中遇到第一个不匹配的字符时，增加偏移量`ofs`，这意味着我们跳过了较长字符串中的一个字符（模拟删除操作），或者跳过了较短字符串中的位置（模拟插入操作）。一旦`ofs`被增加过一次，后续的比较都是基于这个新的偏移进行的。如果再发现不匹配的情况，即`ofs`需要再次增加，这将意味着需要超过一次的编辑操作，因此返回False。这种方法保证了我们只通过一次编辑操作（插入或删除）的模拟来判断两个字符串的相似性。
当两个字符串长度相等时，通过计数不同字符的方法主要是判断是否可以通过一次替换操作使两个字符串相同。这种方法确实考虑了所有可能导致两个等长字符串不同的因素，因为任何不同点都会在字符比较中被计数。如果不同字符的数量超过1，意味着需要多于一次的替换，因此返回False。此方法有效地检测了是否只需要一次替换就能解决问题，因为它直接对应于字符串中不匹配字符的数量。
在长度差为1的情况下，如果在某一点上字符不匹配，并且我们增加了偏移量`ofs`，这意味着我们已经尝试通过跳过较长字符串的一个字符来模拟删除操作，或者跳过较短字符串的一个字符来模拟插入操作。一旦偏移量增加，之前比较过的字符已经被确认是相匹配的，因此不需要重新检查。这种方法的正确性在于，一旦我们应用了一次编辑操作（通过增加偏移量），后续的所有字符应当一一对应相匹配，否则就意味着需要更多的编辑，这将违反题目要求的只允许一次编辑。因此，这种方法确保了一旦发现第一次偏差后的所有字符都必须匹配，从而保证算法的正确性。