NUHMAN.com

Introduction

LeetCode 161 asks us to determine whether two strings are one edit distance apart. An edit can be an insertion, deletion, or replacement of a character. The challenge here is to check if we can transform one string into another by performing only one edit operation.

Problem Statement

Given two strings s and t, return true if they are one edit distance apart, otherwise return false.

Function Signature:

go

func isOneEditDistance(s string, t string) bool

• Input:
• Two strings s and t.
• Output:
• Return true if the strings are one edit distance apart, otherwise return false.

Approach

To solve this problem, we need to consider three types of edit operations:

1. Insertion: One string has an extra character compared to the other.
2. Deletion: One string is shorter than the other by one character.
3. Replacement: Both strings have the same length, but one character is different.

Key Observations:

• If the absolute difference in lengths of the strings is greater than 1, they cannot be one edit distance apart. In that case, we return false immediately.
• If the strings have the same length, we check if there is exactly one character mismatch (replacement).
• If the strings have different lengths, we check if we can make them the same length by either deleting a character from the longer string or inserting a character into the shorter string.

Steps:

1. Length Check: First, check the absolute difference in lengths. If it’s greater than 1, return false immediately.
2. Replacement Case (Same Length): If the strings are the same length, check for exactly one mismatch.
3. Insertion/Deletion Case (Different Length): If the strings are of different lengths, we check if one string can be transformed into the other by either inserting or deleting exactly one character.

Time Complexity:

• O(n) where n is the length of the shorter string. This is because we perform a linear scan to compare characters.

Space Complexity:

• O(1) because we only use a constant amount of extra space.

Go Implementation

go

func isOneEditDistance(s string, t string) bool {
    // If the length difference is greater than 1, return false
    if abs(len(s)-len(t)) > 1 {
        return false
    }

    // If the strings are the same length, check for a single character replacement
    if len(s) == len(t) {
        diffCount := 0
        for i := 0; i < len(s); i++ {
            if s[i] != t[i] {
                diffCount++
            }
            if diffCount > 1 {
                return false
            }
        }
        return diffCount == 1
    }

    // If the strings have different lengths, check for insertion/deletion
    if len(s) > len(t) {
        return isOneEditDistance(t, s) // Ensure s is always the shorter one
    }

    // Check if we can insert one character into s to match t
    for i := 0; i < len(s); i++ {
        if s[i] != t[i] {
            return s[i:] == t[i+1:] // Check if the remainder of the strings match
        }
    }

    // If no differences were found, the strings differ by one character at the end
    return true
}

// Helper function to calculate absolute difference
func abs(a int) int {
    if a < 0 {
        return -a
    }
    return a
}

Explanation of the Code:

1. Length Difference Check:

• We first check if the absolute difference in lengths of s and t is greater than 1. If it is, we return false because it’s not possible to make them equal with just one edit.

2. Same Length Case (Replacement):

• If the two strings are the same length, we iterate over the characters and count how many positions differ. If the number of differences is exactly 1, return true. Otherwise, return false.

3. Different Length Case (Insertion/Deletion):

• If the strings have different lengths, we check if the shorter string can become the longer one by either inserting or deleting one character. We make sure to always pass the shorter string first by swapping s and t if necessary.
• We then compare each character of the shorter string with the corresponding character in the longer string. If a mismatch occurs, we check if the remainder of the strings are identical after skipping one character in the longer string.

4. Helper Function (abs):

• The abs function is used to compute the absolute difference between two numbers. This is useful for comparing the lengths of the two strings.

Example

Example 1:

go

s := "ab"
t := "acb"
result := isOneEditDistance(s, t)
fmt.Println(result) // Output: true

Explanation:

• The strings differ by one insertion: t can be obtained by inserting c at the second position in s.

Example 2:

go

s := "abc"
t := "abcd"
result := isOneEditDistance(s, t)
fmt.Println(result) // Output: true

Explanation:

• The strings differ by one insertion: t can be obtained by inserting d at the end of s.

Example 3:

go

s := "abc"
t := "ab"
result := isOneEditDistance(s, t)
fmt.Println(result) // Output: true

Explanation:

• The strings differ by one deletion: s can be obtained by deleting c from t.

Example 4:

go

s := "abc"
t := "ab"
result := isOneEditDistance(s, t)
fmt.Println(result) // Output: true

Explanation:

• The strings differ by one deletion: s can be obtained by deleting c from t.

Example 5:

go

s := "abc"
t := "xyz"
result := isOneEditDistance(s, t)
fmt.Println(result) // Output: false

Explanation:

• The strings differ by more than one edit, so the output is false.

Conclusion

LeetCode 161 provides an efficient way to check if two strings are one edit distance apart. By carefully checking the lengths and performing comparisons based on the possible edit operations (insertion, deletion, or replacement), we can solve the problem in O(n) time complexity and O(1) space complexity.