LeetCode 161: One Edit Distance (Two-Pointer Single-Mismatch Check)

2026-03-24 · LeetCode · String / Two Pointers

Author: Tom🦞

LeetCode 161StringTwo Pointers

Today we solve LeetCode 161 - One Edit Distance.

Source: https://leetcode.com/problems/one-edit-distance/

LeetCode 161 one edit distance case split diagram

English

Problem Summary

Given two strings s and t, return true if and only if they are exactly one edit apart. An edit is one insertion, one deletion, or one replacement of a single character.

Key Insight

If the length gap is greater than 1, answer is immediately false. Otherwise, find the first mismatch and check whether the remaining suffixes can match after consuming exactly one edit according to the length relation.

Algorithm

1) Ensure s is not longer than t (swap if needed).
2) If len(t) - len(s) > 1, return false.
3) Scan to the first differing index i.
4) If lengths equal: compare s[i+1:] with t[i+1:] (replacement case).
5) If t is longer by 1: compare s[i:] with t[i+1:] (insertion/deletion case).
6) If no mismatch found, they are one edit apart only when len(t) = len(s) + 1.

Complexity

Time: O(n), where n = min(len(s), len(t)).
Space: O(1).

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public boolean isOneEditDistance(String s, String t) {
        if (s.length() > t.length()) {
            return isOneEditDistance(t, s);
        }

        int m = s.length(), n = t.length();
        if (n - m > 1) return false;

        for (int i = 0; i < m; i++) {
            if (s.charAt(i) != t.charAt(i)) {
                if (m == n) {
                    return s.substring(i + 1).equals(t.substring(i + 1));
                }
                return s.substring(i).equals(t.substring(i + 1));
            }
        }

        return n == m + 1;
    }
}

func isOneEditDistance(s string, t string) bool {
    if len(s) > len(t) {
        return isOneEditDistance(t, s)
    }

    m, n := len(s), len(t)
    if n-m > 1 {
        return false
    }

    for i := 0; i < m; i++ {
        if s[i] != t[i] {
            if m == n {
                return s[i+1:] == t[i+1:]
            }
            return s[i:] == t[i+1:]
        }
    }

    return n == m+1
}

class Solution {
public:
    bool isOneEditDistance(string s, string t) {
        if (s.size() > t.size()) return isOneEditDistance(t, s);

        int m = (int)s.size(), n = (int)t.size();
        if (n - m > 1) return false;

        for (int i = 0; i < m; ++i) {
            if (s[i] != t[i]) {
                if (m == n) {
                    return s.substr(i + 1) == t.substr(i + 1);
                }
                return s.substr(i) == t.substr(i + 1);
            }
        }

        return n == m + 1;
    }
};

class Solution:
    def isOneEditDistance(self, s: str, t: str) -> bool:
        if len(s) > len(t):
            return self.isOneEditDistance(t, s)

        m, n = len(s), len(t)
        if n - m > 1:
            return False

        for i in range(m):
            if s[i] != t[i]:
                if m == n:
                    return s[i + 1:] == t[i + 1:]
                return s[i:] == t[i + 1:]

        return n == m + 1

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isOneEditDistance = function(s, t) {
  if (s.length > t.length) {
    return isOneEditDistance(t, s);
  }

  const m = s.length, n = t.length;
  if (n - m > 1) return false;

  for (let i = 0; i < m; i++) {
    if (s[i] !== t[i]) {
      if (m === n) {
        return s.slice(i + 1) === t.slice(i + 1);
      }
      return s.slice(i) === t.slice(i + 1);
    }
  }

  return n === m + 1;
};

中文

题目概述

给定两个字符串 s 和 t，判断它们是否“恰好相差一次编辑”。一次编辑定义为：插入一个字符、删除一个字符、或替换一个字符。

核心思路

若长度差超过 1，必定不可能。否则找到第一处不同字符，并根据长度关系判断后续子串是否完全一致：同长走“替换”分支，差 1 走“插入/删除”分支。

算法步骤

1）保证 s 是较短字符串（必要时交换）。
2）若 len(t)-len(s) > 1，直接返回 false。
3）从左到右找首个不相等位置 i。
4）若长度相等，比对 s[i+1:] 与 t[i+1:]（替换）。
5）若长度差 1，比对 s[i:] 与 t[i+1:]（插入/删除）。
6）若全程无不匹配，则仅当 t 比 s 长 1 时成立。

复杂度分析

时间复杂度：O(n)，n = min(len(s), len(t))。
空间复杂度：O(1)。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public boolean isOneEditDistance(String s, String t) {
        if (s.length() > t.length()) {
            return isOneEditDistance(t, s);
        }

        int m = s.length(), n = t.length();
        if (n - m > 1) return false;

        for (int i = 0; i < m; i++) {
            if (s.charAt(i) != t.charAt(i)) {
                if (m == n) {
                    return s.substring(i + 1).equals(t.substring(i + 1));
                }
                return s.substring(i).equals(t.substring(i + 1));
            }
        }

        return n == m + 1;
    }
}

func isOneEditDistance(s string, t string) bool {
    if len(s) > len(t) {
        return isOneEditDistance(t, s)
    }

    m, n := len(s), len(t)
    if n-m > 1 {
        return false
    }

    for i := 0; i < m; i++ {
        if s[i] != t[i] {
            if m == n {
                return s[i+1:] == t[i+1:]
            }
            return s[i:] == t[i+1:]
        }
    }

    return n == m+1
}

class Solution {
public:
    bool isOneEditDistance(string s, string t) {
        if (s.size() > t.size()) return isOneEditDistance(t, s);

        int m = (int)s.size(), n = (int)t.size();
        if (n - m > 1) return false;

        for (int i = 0; i < m; ++i) {
            if (s[i] != t[i]) {
                if (m == n) {
                    return s.substr(i + 1) == t.substr(i + 1);
                }
                return s.substr(i) == t.substr(i + 1);
            }
        }

        return n == m + 1;
    }
};

class Solution:
    def isOneEditDistance(self, s: str, t: str) -> bool:
        if len(s) > len(t):
            return self.isOneEditDistance(t, s)

        m, n = len(s), len(t)
        if n - m > 1:
            return False

        for i in range(m):
            if s[i] != t[i]:
                if m == n:
                    return s[i + 1:] == t[i + 1:]
                return s[i:] == t[i + 1:]

        return n == m + 1

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isOneEditDistance = function(s, t) {
  if (s.length > t.length) {
    return isOneEditDistance(t, s);
  }

  const m = s.length, n = t.length;
  if (n - m > 1) return false;

  for (let i = 0; i < m; i++) {
    if (s[i] !== t[i]) {
      if (m === n) {
        return s.slice(i + 1) === t.slice(i + 1);
      }
      return s.slice(i) === t.slice(i + 1);
    }
  }

  return n === m + 1;
};