LeetCode 面试题 01.05. 一次编辑
目录
题目描述
题意分析
输入是两个字符串，要判断能否在「最多动一次」的预算内让它们相等。这里的「动一次」有三种形态：往其中一串里插入一个字符、从其中一串里删掉一个字符、把其中一个字符换成别的字符。
注意题面允许的是「一次或零次」，所以两串本来就完全相同也算合法答案，这是最容易被读漏的一句。
从三种操作反推长度关系，是本题最有价值的约束信号：替换不改变长度，插入和删除各让长度变化
1。既然预算只有一次，两串长度差就只能是0或1，任何差值2以上的输入都可以立刻否定。边界上要考虑的输入有：两串完全相同、其中一串为空、两串都为空、长度差恰好为
1、长度差大于1、以及差异出现在末尾（例如"abc"与"ab"）。
解法：双指针比较
核心思路
最直白的暴力做法是把三种编辑全部枚举一遍：对较长串枚举删掉哪一位，对等长的两串枚举改哪一位，每次改完再整体比较一次。枚举位置要 $O(n)$，每次比较又要 $O(n)$，总共 $O(n^2)$，而且三类操作各写一段，代码又长又容易漏分支。
瓶颈在于「改完再整体比较」这件事重复做了太多次。观察被枚举的这些候选：它们的公共前缀其实是同一段，真正的分歧点只有一个。既然预算只有一次编辑，两串从左往右扫描时，第一次失配之前的部分必然逐位相等，第一次失配的位置就是唯一要花掉预算的地方。花完之后，剩下的部分必须逐位严格相等，不允许再有第二次失配。
于是只需要一趟扫描。先统一把较短的串放在
first，较长的放在second，这样插入和删除就归并成了同一件事：短串少了一个字符，等价于在长串上跳过一个字符。显式的不变量是：扫描到任意时刻，
first[0..i)都可以通过已经花掉的edits次编辑变成second[0..j)，并且edits <= 1。字符相同时两个指针同步前进，不变量自然保持；字符不同时花掉一次预算，此时edits会变成1，指针的走法由长度关系决定——等长就是替换，两个指针一起走；不等长就是长串多了一个字符，只让j前进跳过它。一旦edits要变成2，不变量被破坏，直接返回false。
解题步骤
- 先算两串长度差，大于
1就返回false。这一步不是优化而是正确性前提：后面的循环会在短串走到头时自然退出，如果长度差是3，循环会在edits还是0的时候结束并错误地返回true。- 若
first比second长，交换参数再递归调用一次。这样做是为了让后续代码只需要处理「短串在前」这一种形态，把插入和删除合并成同一条分支。- 用
i指向first、j指向second，edits记录已花掉的编辑次数，循环条件是两个指针都没越界。- 当
first[i] == second[j]时两个指针同时后移。这一步不消耗预算，因为这一位不需要任何编辑。- 当两个字符不同时
edits加一，若已经超过1立刻返回false。之所以能立刻返回，是因为不变量要求全程edits <= 1。- 失配后若两串等长则
i也后移，否则只移动j。等长意味着这一位只能用替换解决，两边都要跳过；不等长意味着second多出一个字符，跳过它就让剩余部分重新对齐。- 循环退出后直接返回
true。此时要么短串已经走完，要么中途已经因为edits超标返回了false，剩余的至多一个字符正好被那次尚未使用或已经使用的预算覆盖。以
first = "pale"、second = "ple"走一遍：长度差是 $4 - 3 = 1$，不大于1，通过预判。因为first更长，交换后变成first = "ple"、second = "pale"，此时i = 0、j = 0、edits = 0。第一轮'p'对'p'相等，i = 1、j = 1。第二轮first[1] = 'l'对second[1] = 'a'不等，edits变成1，两串长度3与4不等，所以只移动j，得到i = 1、j = 2。第三轮first[1] = 'l'对second[2] = 'l'相等，i = 2、j = 3。第四轮first[2] = 'e'对second[3] = 'e'相等，i = 3、j = 4。此时i等于first长度3，循环退出，返回true，对应的编辑正是从"pale"中删掉'a'。再看反例
first = "abcd"、second = "ab"：长度差是2，第一步就返回false，循环根本不会执行。
代码实现
class Solution {
public boolean oneEditAway(String first, String second) {
if (Math.abs(first.length() - second.length()) > 1) {
return false;
}
if (first.length() > second.length()) {
return oneEditAway(second, first);
}
int i = 0;
int j = 0;
int edits = 0;
while (i < first.length() && j < second.length()) {
if (first.charAt(i) == second.charAt(j)) {
i++;
j++;
} else {
edits++;
if (edits > 1) {
return false;
}
if (first.length() == second.length()) {
i++;
}
j++;
}
}
return true;
}
}
func oneEditAway(first string, second string) bool {
if absInt(len(first)-len(second)) > 1 {
return false
}
if len(first) > len(second) {
return oneEditAway(second, first)
}
i, j := 0, 0
edits := 0
for i < len(first) && j < len(second) {
if first[i] == second[j] {
i++
j++
} else {
edits++
if edits > 1 {
return false
}
if len(first) == len(second) {
i++
}
j++
}
}
return true
}
func absInt(x int) int {
if x < 0 {
return -x
}
return x
}
复杂度分析
- 时间复杂度：$O(n)$，$n$ 是较短串长度。每轮循环至少让
j前进一格，j最多走 $n + 1$ 步就会让循环因为i或j越界而退出，交换参数的递归只会发生一次。- 空间复杂度：$O(1)$，只用了两个下标和一个计数器，没有开辟与输入规模相关的额外结构；那次交换参数的递归深度也是常数。
关键点总结
- 先从操作的「代数性质」反推约束，再动手写循环。替换保长度、插删改长度
1，这条推理直接给出了长度差不超过1的硬性剪枝，比在循环里补丁式地打各种判断可靠得多。- 遇到「A 和 B 对称」的两种操作，优先用规范化把它们合并。这里把短串强制放到
first，插入和删除立刻塌缩成同一条分支，代码量和出错面同时减半。- 双指针的核心是想清楚「失配之后谁动」。等长动两个、不等长只动长串，这个决策规则本身就是本题的全部难点，写代码前应该先用一句话把它说出来。
- 把不变量写成「前缀已经用
edits次编辑对齐且edits <= 1」，循环退出时的正确性就不需要额外讨论，这是所有一趟扫描类题目通用的论证套路。- 面试视角：这题是编辑距离的 $k = 1$ 特例，面试官几乎一定会追问「改成最多
k次编辑呢」。正确回答是当k变大后一趟扫描的贪心不再成立，要退回 $O(mn)$ 的编辑距离动态规划，或者用带状 DP 只算主对角线附近 $2k + 1$ 条带做到 $O(kn)$。能讲清「为什么 $k = 1$ 才能线性」比写对代码更加分。- 面试视角：白板上先说剪枝与不变量再落笔，中途主动补一句「零次编辑也算合法」，能直接展示对题面边界的敏感度，这是这道简单题唯一的观察点。
易错点总结
- 错误写法：省略长度差预判，循环跑完就
return true。用例first = "ab"、second = "abcde"→ 两串前缀完全相同，循环因为i走到first末尾而退出，edits全程是0，返回true，但实际需要三次插入，答案应为false。- 错误写法：不做「短串换到前面」的归一化就直接进循环。用例
first = "pale"、second = "ple"→ 第二轮'a'对'l'失配，长度不等的分支只推进j，而此时j指向的是短串，指针越走越错位，第三轮再次失配使edits变成2，返回false，正确答案是true。- 错误写法：失配后无论长度关系一律同时移动两个指针。用例
first = "ple"、second = "pale"→ 第二轮'l'对'a'失配后i也跟着前进，后续变成'e'对'l'再次失配，edits达到2返回false，正确答案是true。- 错误写法：失配后只移动短串指针
i。用例first = "ple"、second = "pale"→j一直停在'a'上，第三轮'e'对'a'又一次失配，返回false，正确答案是true。- 错误写法：把「恰好一次编辑」当成合法条件，要求
edits == 1才返回true。用例first = "abc"、second = "abc"→ 全程没有失配，edits是0，被判为false，但题目明确允许零次编辑。- 错误写法：长度差的判断写成
abs(len1 - len2) != 1才继续。用例first = "ab"、second = "ab"→ 长度差为0直接被拒，所有等长的替换场景和相同串场景全部误判为false。- 错误写法：交换分支里递归调用时参数没有真正换位，写成
oneEditAway(first, second)。用例first = "pale"、second = "ple"→ 每次进入都满足first更长的条件，无限递归直到栈溢出。- 错误写法：把边界写成
abs(len1 - len2) >= 1就返回false。用例first = "pale"、second = "ple"→ 长度差恰为1的插入删除场景被整类排除，只剩等长替换能通过，答案错成false。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 72. 编辑距离 | 中等 | 编辑次数不设上限，需要二维 dp 求最少操作数 |
| 583. 两个字符串的删除操作 | 中等 | 只保留删除操作，等价于求最长公共子序列后取补 |
| 392. 判断子序列 | 简单 | 允许任意多次跳过，双指针不再受编辑预算约束 |
| 680. 验证回文串 II | 简单 | 同样是一次删除预算，但指针从两端相向而不是同向 |