⚡Flashcard Drill➔
NeetCode #27LC-161MediumArrays & HashingNC Algo100
← Back to All Problems

#27 · #161 · One Edit Distance(相隔为 1 的编辑距离)

📌 Problem Statement & Constraints

Given two strings s and t, determine whether they are exactly one edit distance apart. A valid edit is inserting one character, deleting one character, or replacing one character. Constraints: 0 <= s.length, t.length <= 10^4.

💡 Core Algorithmic Approaches

  1. If the length difference exceeds 1, no single edit can bridge them -- return false immediately.
  2. Normalise so that s is the shorter string. Then the only possible operations are a replacement (equal lengths) or an insertion into s (t is one longer).
  3. Advance both pointers while the characters match; call the first mismatch position i.
  4. If i reaches the end of the shorter string, the strings agree on the whole prefix, so the answer is len(t) - len(s) == 1 -- an insertion at the end. Otherwise skip one character in the longer string (for an insertion) or in both (for a replacement) and check that the remainders match exactly.
  5. Note that equal strings are not one edit apart, which is why the length check comes first.

💻 Benchmark Python3 Implementation

class Solution:
    def isOneEditDistance(self, s: str, t: str) -> bool:
        if abs(len(s) - len(t)) > 1:
            return False
        if len(s) > len(t):
            s, t = t, s                    # s is the shorter string
        i = 0
        while i < len(s) and s[i] == t[i]:
            i += 1
        if i == len(s):
            # shorter string fully matched: valid only if t has exactly one extra char
            return len(t) - len(s) == 1
        if len(s) == len(t):
            return s[i + 1:] == t[i + 1:]  # replacement at position i
        return s[i:] == t[i + 1:]          # insertion into s at position i

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(min(|s|, |t|)): one pass to locate the first mismatch, plus one slice comparison whose total length is bounded by the shorter string.
💾 Space Complexity
O(min(|s|, |t|)) for the slice comparisons; a pointer-based comparison would be O(1).

⚠️ Interview Pitfalls & Follow-ups

  • Returning true for identical strings: identical strings are zero edits apart, not one. The i == len(s) branch must require len(t) - len(s) == 1.
  • Not normalising the length order: handling both the insertion and deletion directions separately doubles the branches and invites bugs.
  • Using abs(len(s) - len(t)) >= 1 as the early exit: the threshold is > 1; a difference of exactly 1 is the interesting case.
  • Comparing only up to the mismatch: the suffix after the edit must match exactly, otherwise the strings differ in more than one place.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Arrays & Hashing Problems