面试题 01.05. 一次编辑

大家好，我是 @负雪明烛。👈👈 点击关注，优质题解不间断。

题目大意

一次编辑操作可以是：增加、删除、替换一个字符。
判断两个字符串能否可以通过一次或零次编辑操作互相得到。

今天的题目很好懂，直接开干。

解题方法

情况分析

我拿到这个题目的第一想法是按「统计词频」的方法做，但即使「词频」相差小于等于 1，还有排列顺序的问题，因此必须放弃这个做法。

首先我们可以把字符串长度相差大于 的，都排除掉。比如示例 2 "pales"和 "pal"。

现在 和 长度相等或者长度相差 .

如果 能通过一次或者零次编辑得到 ，则可能有下面 3 种情况：

1. 假如和 长度相等：
   1. 两者可能完全相等，即通过零次编辑得到。
   2. 两者中只有一个字符不等，即通过一次替换操作得到。（如 first = "abc"和 second = "abe"）
2. 假如的长度比 长度大：
   1. 只能是删除 中的一个字符得到 ；（如 first = "abc"和 second = "ac"）
3. 假如的长度比 长度大：
   1. 交换两者，即变成了情况 2.（如 first = "ac"和 second = "abc"）

问题拆解以后，思路是不是清晰很多了？

解法：双指针

如果两者的字符长度差距大于 $1$，直接不符合题意。

那么，现在两个字符串就最多只有一个字符不同，我们使用双指针求和之间的 即可。

用两个指针分别指向 和 的两个字符，根据字符的是否相等，判断移动哪个指针。

我们只考虑 长度与 相等或者 长度比大 的情况，下面画图分析：

1. 长度与 相等

两个指针一起从左向右移动，每次各移动一步，当遇到不等的字符时仍然继续都右移。

统计不同的字符个数 。

符合要求的 。

1. 长度比 大 1

两个指针一起从左向右移动，每次各移动一步，当遇到不等的字符时 右移，原地等待一次。

统计不同的字符个数 。

符合要求的 。

1. 长度比 大 1

交换两者，转换成情况 2 处理。

代码

上面的思路理解以后，代码还是很好写出的。

1. 先判断长度相差 $> 1$，直接返回 $False$
2. 如果 长度等于 长度 $+ 1$，则交换两者，仍然调用该函数。
3. 使用双指针分别指向 和 ，每次都向右移动一步
   1. 当两者指向的字符不同时，diff ++，如果比 长度大 $1$，则让 原地等待。
   2. 当 时，返回
4. 当比较完成之后，仍然没有发现 ，说明可以通过一次编辑得到，返回 $True$

代码如下：

class Solution(object):
    def oneEditAway(self, first, second):
        M, N = len(first), len(second)
        if abs(M - N) > 1:
            return False
        if N == M + 1:
            return self.oneEditAway(second, first)
        i, j = 0, 0
        diff = 0
        while i < M and j < N:
            if first[i] != second[j]:
                diff += 1
                if diff >= 2:
                    return False
                if M > N:
                    j -= 1 # 为了让原地等待，先回退一步，后面会再向右移动一步
            i += 1 # 每次都向右移动一步
            j += 1 # 每次都向右移动一步
        return True

复杂度

• 时间复杂度：$O(N)$，是字符串长度。
• 空间复杂度：$O(1)$，没用额外空间。

  总结

1. 今天这个题主要是分情况讨论，想明白各种情况，思路清晰了的话，代码不难。

我是 @负雪明烛 ，刷算法题 1000 多道，写了 1000 多篇算法题解，收获阅读量 300 万。
关注我，你将不会错过我的精彩动画题解、面试题分享、组队刷题活动，进入主页 @负雪明烛 右侧有刷题组织，从此刷题不再孤单。

• 在刷题的时候，如果你不知道该怎么刷题，可以看 LeetCode 应该怎么刷？
• 如果你觉得题目太多，想在短时间内快速提高，可以看 LeetCode 最经典的 100 道题。
• 送你一份刷题的代码模板：【LeetCode】代码模板，刷题必会
• 我写的 1000 道 LeetCode 题解，都在这里了，免费拿走。