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
- If the length difference exceeds 1, no single edit can bridge them -- return
falseimmediately. - Normalise so that
sis the shorter string. Then the only possible operations are a replacement (equal lengths) or an insertion intos(t is one longer). - Advance both pointers while the characters match; call the first mismatch position
i. - If
ireaches the end of the shorter string, the strings agree on the whole prefix, so the answer islen(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. - 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
truefor identical strings: identical strings are zero edits apart, not one. Thei == len(s)branch must requirelen(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)) >= 1as 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.