LeetCode 161. 相隔为 1 的编辑距离

2026-05-24 HGNULB 约 6 分钟

文章信息 2 个分类 2 个标签

分类

LeetCode 中等

题目描述

✅ 161. 相隔为 1 的编辑距离

题意分析

判断字符串 s 和 t 的编辑距离是否恰好等于 1。一次编辑只能是三种操作之一：插入一个字符、删除一个字符、替换一个字符。

“恰好一次”是本题最容易漏掉的条件："abc" 与 "abc" 的编辑距离是 0，必须返回 false；"abc" 与 "ab" 可以删除一个字符，返回 true。

长度差已经给出第一层剪枝。一次编辑最多改变一个字符长度，所以 |m-n| > 1 必然为 false；长度相等时唯一可能是替换，不等时唯一可能是在较长串中删除一个字符（等价于向较短串插入一个字符）。

因而没有必要使用完整的编辑距离动态规划。两个指针从左向右扫描，第一次不匹配时根据长度关系跳过一个或两个字符；若再次不匹配，答案就是 false。

解法：双指针统计唯一编辑

核心思路

用 i、j 分别指向 s、t 尚未匹配的第一个字符，并用 edits 记录已经消耗的编辑次数。

循环不变量是：s[0, i) 与 t[0, j) 已经能够通过恰好 edits 次编辑匹配，且 edits 不超过 1。

当前字符相同，两个指针一起前进，不消耗编辑。当前字符不同则消耗一次编辑：长度相等时视为替换，两个指针都前进；s 更长时跳过 s[i]，视为删除；t 更长时跳过 t[j]，视为向 s 插入该字符。

循环写成 i < m || j < n，这样其中一个字符串先结束时，另一个字符串尾部多出的单个字符也会被计为一次编辑。最终必须检查 edits == 1，从而排除两个字符串完全相同的情况。

解题步骤

计算长度 m、n，若绝对差大于 1，直接返回 false。

初始化 i = 0、j = 0、edits = 0。

两边字符都存在且相等时，同时推进 i 和 j。

否则令 edits++；超过 1 立即返回 false。

根据 m 与 n 的关系推进较长串指针，或在等长时同时推进。

扫描结束后返回 edits == 1。

以 s = "ab"、t = "acb" 为例：a 匹配后到达 b 与 c，两串长度不同，所以把这次编辑解释成向 s 插入 c，只推进 t 的指针；随后两个 b 匹配，最终只用一次编辑，返回 true。

对 s = "abc"、t = "adc"，只有 b → d 一次替换，返回 true；对两个完全相同的 "abc"，扫描结束时 edits = 0，返回 false。

代码实现

class Solution {
    public boolean isOneEditDistance(String s, String t) {
        int m = s.length(), n = t.length();
        if (Math.abs(m - n) > 1) {
            return false;
        }

        int i = 0, j = 0, edits = 0;
        while (i < m || j < n) {
            if (i < m && j < n && s.charAt(i) == t.charAt(j)) {
                i++;
                j++;
                continue;
            }

            if (++edits > 1) {
                return false;
            }
            if (m > n) {
                i++;       // 删除 s[i]
            } else if (m < n) {
                j++;       // 向 s 插入 t[j]
            } else {
                i++;       // 替换 s[i] 为 t[j]
                j++;
            }
        }
        return edits == 1;
    }
}

func isOneEditDistance(s string, t string) bool {
    m, n := len(s), len(t)
    if m-n > 1 || n-m > 1 {
        return false
    }

    i, j, edits := 0, 0, 0
    for i < m || j < n {
        if i < m && j < n && s[i] == t[j] {
            i++
            j++
            continue
        }

        edits++
        if edits > 1 {
            return false
        }
        if m > n {
            i++ // 删除 s[i]
        } else if m < n {
            j++ // 向 s 插入 t[j]
        } else {
            i++ // 替换 s[i] 为 t[j]
            j++
        }
    }
    return edits == 1
}

复杂度分析

时间复杂度：$O(m+n)$，两个指针都只向右移动，每个字符最多比较一次；长度差大于 1 时为 $O(1)$。

空间复杂度：$O(1)$，只使用三个整数状态。Java 实现没有创建 substring，因此不会因复制后缀产生额外的 $O(m+n)$ 空间。

关键点总结

长度差决定第一次不匹配时该执行替换还是插入/删除，这是从题意到指针移动的直接映射。

必须统计“恰好一次”，所以最后判断 edits == 1，不能只判断 edits <= 1。

用 || 扫描可以统一处理尾部多出一个字符，不需要另写尾部特判。

这道题只问距离是否为 1，完整编辑距离 DP 会使用 $O(mn)$ 时间，属于明显过度设计。

Go 代码按字节比较，适用于题目给定的 ASCII 字符串；若面试官把输入扩展为任意 Unicode，应先转成 []rune 再使用同样的双指针逻辑。

易错点总结

把“恰好一次”写成“至多一次”："abc" 与 "abc" 会被误判为 true，正确答案是 false。

忽略长度差剪枝："a" 与 "abc" 至少需要两次插入，不可能只靠一次跳过解决。

第一次不匹配时总是同时推进："ab" 与 "acb" 应只跳过较长串中的 c；同时推进后会继续比较 b 与 b 之前的错误位置。

只循环到较短串结束且直接返回："ab" 与 "a" 的唯一编辑发生在尾部，若不处理剩余字符会漏判。

使用 substring 比较剩余后缀并宣称空间 $O(1)$：现代 Java 会复制子串内容，最坏产生线性额外空间；逐字符双指针才能保证 $O(1)$。

使用编辑距离 DP：虽然能得到正确答案，但时间和空间都从线性退化到 $O(mn)$，面试中应先利用“只允许一次编辑”的强约束。

相似题目

题目	难度	考察点
72. 编辑距离	中等	求任意编辑距离，需要二维动态规划
392. 判断子序列	简单	双指针允许跳过多个字符，可对照本题只允许跳过一次
583. 两个字符串的删除操作	中等	只允许删除，通过最长公共子序列计算最少次数
680. 验证回文串 II	简单	只允许删除一个字符，第一次不匹配后分支验证
844. 比较含退格的字符串	简单	双指针跳过失效字符并比较最终序列