161. One Edit Distance
Model: qwen3.5:9b
Topics: String
FAANG asked: 1
Acceptance rate: 33.2%
Problem Breakdown
We need to determine if two strings, s and t, differ by exactly one edit operation. The allowed operations are inserting a character into s, deleting a character from s, or replacing a character in s.
Inputs: Two strings s and t.
Output: A boolean (True if valid, False otherwise).
Implicit Constraints & Edge Cases:
- Empty Strings: If both are empty, distance is zero (not one), so return
False. If one is empty and the other has length > 0, it’s only true if the non-empty string has length exactly 1. - Length Difference: The absolute difference in lengths must be at most 1. If they differ by more than 1 character count, no single edit can bridge them (e.g., deleting one char from a short string won’t make it longer).
- Identical Strings: If
sequalst, the distance is zero, so returnFalse.
Intuition
First, I’d consider brute-forcing by trying all three operations at every position. That would involve nested loops or recursion, leading to time complexity, which isn’t acceptable for strings up to length 10,000 in an interview setting where we aim for linear solutions.
The key insight is that the two pointers approach allows us to compare characters sequentially from left to right until a mismatch occurs or one string ends.
- If there’s no mismatch while iterating through both strings simultaneously (up to the length of the shorter string), then either they are identical (0 edits) or we need an insertion at the very end if lengths differ by 1.
- Once we hit a mismatch, say
s[i] != t[j], this is our “edit point”.- If
len(s)andlen(t)are equal, it must be a replacement. We just skip both characters (i+1vsj+1) to see if the rest matches. - If one string is longer by 1 (say
s), we assume an insertion happened intot. Since we can’t insert intos, this implies a deletion froms. We skip only the character in the longer string (i+1) and compare against the current char of the shorter string. - If one is shorter, it’s effectively inserting into the shorter to match the longer (or deleting from longer).
- If
This reduces us to finding the first mismatch index once, then validating if the remaining suffixes align after skipping exactly one character in the appropriate string.
Approach
- Length Check: Immediately return
Falseifabs(len(s) - len(t)) > 1. This is a hard constraint for “one edit”. - Pointer Iteration: Iterate through both strings using indices
iandj. Stop at the first mismatch or when we reach the end of the shorter string. - Mismatch Handling:
- If no mismatch found during iteration: Return
Trueonly if lengths differ by exactly 1 (insertion/deletion at the very end). Otherwise, they are identical strings (False). - If a mismatch is found: Check which string is longer.
- If
len(s) == len(t)(Replace): We assume replacement happened here. Since we need to verify if exactly one edit occurred and no further edits exist in the suffix, technically any single char difference followed by matching rest implies replace works? Wait, strictly: Replace means current chars differ but subsequent must match. Actually, simpler logic: If mismatch found ati, check if remaining substrings match after skipping one index of the longer string (or both for replacement). - To keep code clean and Pythonic without complex pointer swapping inside loops, we can handle cases based on length difference directly in a single pass or use slicing. Given constraints (), slicing is acceptable but I will implement logic that avoids unnecessary copies where possible by checking indices.
- If
- Refined Logic:
- Ensure
sandtare handled such that we check the longer string against shorter if lengths differ, or just iterate normally. - Actually, standard optimal approach: Iterate until mismatch. If no mismatch found after loop, return True only if length diff is 1.
- On mismatch at index
i:- If
len(s) > len(t)(Delete from s): Checks[i+1:] == t[j:]. - Else (
len(s) <= len(t): Insert into s / Replace: Checks[i:] == t[j+1:].
- If
- Ensure
- If no mismatch found during iteration: Return
Complexity Analysis
- Time: , where is the length of the longer string. We iterate through both strings once to find the mismatch or reach the end. The slicing check (if used) happens at most once after finding a mismatch, keeping it linear overall.
- Space: auxiliary space if we use indices and avoid creating new substrings during iteration logic (though Python string slicing creates copies, in an interview context this is often accepted for readability; strictly speaking to be optimal on memory, one would compare characters directly). I will write the solution using direct comparison or minimal allocation.
Solution
def isOneEditDistance(s: str, t: str) -> bool:
# 1. Handle length constraint immediately
if abs(len(s) - len(t)) > 1:
return False
# Ensure s is the longer string (or equal) to simplify logic for insertion/deletion check
# If we swap, we just need to ensure our comparison logic handles "s" as potentially shorter.
# However, standard approach often iterates on min_len and checks suffixes of max_len.
n = len(s)
m = len(t)
i, j = 0, 0
while i < n and j < m:
if s[i] == t[j]:
i += 1
j += 1
else:
# Mismatch found.
# If lengths are equal -> Replace (skip both)
# If len(s) > len(t) -> Delete from s (skip only s's char, check rest of s vs t)
# If len(s) < len(t) -> Insert into s / skip t's char
if n == m:
return s[i+1:] == t[j+1:]
elif n > m:
return s[i+1:] == t[j:]
else:
# m > n (t is longer)
return s[i:] == t[j+1:]
# If we exit loop, one string might be exhausted.
# Check if remaining characters match or length diff allows insertion at end.
# Case 1: No mismatch found in the overlapping part.
# Valid only if lengths differ by exactly 1 (insertion/deletion happened after last matched char).
return abs(n - m) == 1
Edge Cases Handled
- Both Empty:
lencheck passes, loop doesn’t run or runs fully matching? If both empty,n=0,m=0. Loop condition fails immediately. Returnsabs(0-0)==1-> False. Correct (Example 2). - One Empty (
s="",t="A"): Length diff is 1. Loop doesn’t run or runs for min_len (0). Mismatch logic skipped? Wait, if loop condition fails immediately because one string empty: The code falls through to return check at end. If lengths differ by 1 -> True. Correct (Example 4/3). - Identical Strings:
s="abc",t="abc". Loop runs fully without mismatch. Returnsabs(0)==1-> False. Correct. - Mismatch at End: e.g.,
s="ab", t="ac". Mismatch found, suffixes empty or match? Logic handles replacement check correctly via slicing/indices.