Given two strings s
and t
, determine if they are at most one edit distance apart. One edit distance means you can perform one of the following operations on s
to obtain t
:
s
.s
.s
with a different character.The solution employs a concise approach that leverages string comparison to efficiently determine if the edit distance is one. Here's a breakdown:
Handle Length Differences: The function first checks the lengths of s
and t
. If the absolute difference in lengths is greater than 1, it's impossible to achieve one edit distance, so false
is returned. This handles cases where more than one insertion or deletion would be necessary.
Iterate and Compare: The code iterates through the shorter string (t
in this case after potential swapping). In each iteration, it compares the characters at the current index in both strings.
Edit Found: If a mismatch (s[i] != t[i]
) is found:
m == n
), it means a replacement is the only possibility. The function then checks if the remaining substrings (s[i+1:]
and t[i+1:]
) are identical. If they are, a single replacement was sufficient; otherwise, more edits are needed. If the lengths are different (m != n
), it checks if s[i+1:]
is equal to t[i:]
(indicating a deletion from s or insertion into t).No Edits Needed: If the loop completes without finding any mismatches, it means the strings are either identical or differ only by an extra character at the end of the longer string (meaning a single insertion or deletion is sufficient).
class Solution:
def isOneEditDistance(self, s: str, t: str) -> bool:
m, n = len(s), len(t)
if abs(m - n) > 1:
return False
if m < n:
s, t = t, s # Ensure s is the longer or equal-length string
m, n = n, m
i = 0
diff_count = 0
while i < n:
if s[i] != t[i]:
diff_count += 1
if diff_count > 1:
return False
if m > n: # Handle insertion/deletion case
i += 1 # Skip ahead in the longer string
i += 1
return diff_count == 1 or (m == n + 1 and diff_count == 0) # handle insertion/deletion or no differences with extra character
The Python code directly implements the logic explained above. Other languages would follow a very similar structure, adapting syntax and string manipulation functions as necessary. (See the Java, C++, Go, and TypeScript examples provided in the original response)