161. One Edit Distance

Problem Description

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:

• Insert: Insert a character into s.
• Delete: Delete a character from s.
• Replace: Replace a character in s with a different character.

Solution Explanation

The solution employs a concise approach that leverages string comparison to efficiently determine if the edit distance is one. Here's a breakdown:

1. 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.

2. 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.

3. Edit Found: If a mismatch (s[i] != t[i]) is found:

   • Replacement or Insertion/Deletion: If the lengths are equal (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).

4. 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).

Time and Space Complexity

• Time Complexity: O(min(m, n)), where 'm' and 'n' are the lengths of strings 's' and 't' respectively. The algorithm iterates through the shorter string at most once.
• Space Complexity: O(1). The algorithm uses a constant amount of extra space.

Code Implementation (Python)

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)