LeetCode 面试题 01.05. 一次编辑

约 5 分钟
文章信息 9 个分类 2 个标签
分类
LeetCode CodeTop 中等 未解决 5-10 程序员面试金典（第 6 版） 腾讯 字节 华为
标签
字符串 双指针

题目描述

✅ 面试题 01.05. 一次编辑

image-20260929000710650

题意分析

判断两个由英文字符组成的字符串，能否通过至多一次插入、删除或替换变得相等。允许零次编辑，因此原本相同的字符串也应返回 true。

解法：双指针比较

核心思路

[!blue]

一次插入或删除只改变一个字符的长度，替换不改变长度。因此长度差大于一时一定无解；其余情况将较短串统一放在 first，较长串放在 second，只需考虑等长与相差一两种情况。

用 i、j 分别指向两串还未处理的字符，edits 记录已用的编辑次数。当前字符相同，就保留这一对并让两个指针同时前进。第一次失配时，长度关系已经决定了唯一可能的操作类型，无需像一般编辑距离那样枚举三种分支。

若两串等长，一次插入或删除都会让长度不再相等，只能替换当前字符。因此同时跳过两边的失配字符，相当于把它们改成相同字符，再比较后缀。

若长度相差一，唯一一次编辑必须用于删除长串中的一个字符，或等价地向短串插入它。已有前缀都相同，若要修复当前失配，就应跳过 second[j]，只让 j 前进，保留 first[i] 等待与长串的下一个字符比较。两种情况都会消耗一次编辑，此后再遇失配就直接失败。

循环结束后无需额外统计尾部：等长时两个指针始终同步，必然同时结束；长串多一位时，如果中途已经跳过一个字符，此后始终有 j = i + 1，也会同时结束。如果中途一直匹配，则长串恰好剩最后一个字符，而编辑次数仍为零，正好可用一次插入或删除处理。因此到达循环末尾就能返回 true，空串情形也由长度检查和这个结论自然覆盖。

解题步骤

  1. 长度差超过一就返回 false；若 first 更长，交换参数后再处理。
  2. 从 i = 0、j = 0 开始比较。相同则两个指针一起前进。
  3. 不同则增加 edits；若超过一，立即返回 false。
  4. 等长时两侧都跳过当前字符；不等长时只跳过长串当前字符。
  5. 没有第二次失配而结束比较，就返回 true。

代码实现

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(\min(m,n)+1)$，其中 m、n 是两串长度。每次匹配都推进短串指针，失配至多多跳过一个长串字符；交换参数最多发生一次。
  • 空间复杂度：$O(1)$。只有两个下标和编辑计数，参数交换也只增加常数层调用。

关键点总结

[!green]

  • 长度相等时只可能替换，长度相差一时只可能插入或删除。
  • 第一次失配按长度关系恢复后缀对齐，之后必须完全匹配。
  • 末尾是否还剩字符，与此前是否已用编辑由指针位置自动对应。

易错点总结

[!yellow]

  • 省略长度差检查，会把过长的剩余后缀误认为一次编辑就能处理。
  • 长度不等时同时移动两个指针，会跳过短串中本来还要比较的字符。
  • 长度相等时只移动一侧，会把替换错误地当成插入或删除。
  • 题目要求“至多一次”，不能拒绝完全相同的字符串或两个空串。

相似题目

题目 难度 关联与区别
161. 相隔为 1 的编辑距离 中等 原题要求恰好一次编辑，本题允许至多一次，因此两个本就相同的字符串应返回true。
72. 编辑距离 中等 原题计算任意编辑距离，本题上限只有1，可由长度关系直接决定首次失配时的指针移动。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2023/16636749
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！