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

2026-05-24 HGNULB 约 5 分钟

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

分类

LeetCode 中等会员题

题目描述

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

题意分析

判断 s 与 t 能否通过恰好一次插入、删除或替换变成相同字符串。完全相同的两个字符串编辑距离为 0，所以应返回 false。

一次编辑最多改变一个字符的长度，因此长度差大于 1 时不可能满足。长度相等时只能用一次替换；长度相差 1 时，只能向较短串插入字符，等价于从较长串删除字符。

这个限制使我们不需要计算完整编辑距离：从左往右比较，首次不同时，根据原始长度关系唯一确定应跳过哪一边。后续部分必须完全匹配，否则一次编辑不够。

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

核心思路

[!blue]

i、j 分别指向两串下一个待匹配的位置，edits 记录已经使用的编辑次数。开始时两个位置都为 0，也没有消耗编辑。

若两边都有字符且相等，同时前进。若不同，则必须用一次编辑处理当前位置：等长时同时跳过两个字符，表示替换；s 较长时只跳过 s[i]，表示删除；t 较长时只跳过 t[j]，表示插入到 s。

为什么不需要尝试其他跳法？首次失配以前的前缀已经相同；剩下只有一次操作，而且长度差已经确定操作类型。等长串用插入或删除会产生无法修复的长度差，不等长串用替换则无法消除长度差。因此每次移动都有唯一依据。

循环条件使用 i < m || j < n，只要一边没结束就继续。这让尾部多出来的字符也进入失配分支，消耗一次编辑；读取字符前则分别检查下标，避免越界。第二次失配立刻返回 false，最终仅在 edits == 1 时返回 true。

解题步骤

记录原长度 m、n，长度差超过 1 则直接返回 false。

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

当前字符相同，就同时推进两个指针。

否则增加编辑次数，超过 1 则失败；按长度关系推进较长串的指针，等长时推进两边。

两串均扫描完后，检查是否恰好使用了一次编辑。

对 "ab" 与 "acb"，匹配 a 后遇到 b、c，只推进较长串跳过 c，随后两个 b 匹配。对空串与单字符字符串，循环直接把唯一字符计为一次编辑；两个空串则一次也不编辑，返回 false。

代码实现

class Solution {
    public boolean isOneEditDistance(String s, String t) {
        int m = s.length();
        int n = t.length();

        if (Math.abs(m - n) > 1) {
            return false;
        }

        int i = 0;
        int j = 0;
        int 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) {
                // 删除 s[i]
                i++;
            } else if (m < n) {
                // 向 s 插入 t[j]
                j++;
            } else {
                // 替换 s[i] 为 t[j]
                i++;
                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 {
            // 删除 s[i]
            i++
        } else if m < n {
            // 向 s 插入 t[j]
            j++
        } else {
            // 替换 s[i] 为 t[j]
            i++
            j++
        }
    }
    return edits == 1
}

复杂度分析

时间复杂度：$O(m+n)$，两个指针始终向右移动，每轮至少推进一个；长度差超过 1 时直接结束。

空间复杂度：$O(1)$，只保存长度、位置和编辑计数，不创建字符数组或后缀子串。

关键点总结

[!green]

使用原始长度差判断操作类型，第一次跳过后无需重新计算后缀长度。

失配时只推进被删除或被插入一侧的指针，另一侧仍需参与下一轮匹配。

edits == 1 同时排除了完全相同与需要多次编辑的字符串。

Java 按 char、Go 按字节比较；这里沿用本篇题意中的 ASCII 字符输入范围。

易错点总结

[!yellow]

返回 edits <= 1：会把两个完全相同的字符串误判为符合要求。

失配后一律同时推进：长度不等时应保留较短串当前位置，否则会错过仍可匹配的字符。

只扫描到较短串结尾：可能漏掉较长串末尾的唯一额外字符，需要另行处理；当前 || 循环已把它统一计入。

在检查下标前读取字符：一边结束而另一边仍有字符是合法边界，必须先做范围检查。

通过复制后缀比较却仍标为常数空间：这类实现可能创建线性大小的中间字符串，当前双指针没有该开销。

相似题目

题目	难度	关联与区别
72. 编辑距离	中等	原题求任意编辑距离，本题只验证距离1，可用长度关系直接决定指针移动。
680. 验证回文串 II	简单	同样在首次失配处处理一次操作，原题只允许删除并要求回文，本题还允许插入和替换。

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2026/63461304

许可本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！