161. One Edit Distance

Thoughts and Talk

Problem Statement

1. The strings have the same length, and they differ by exactly one character at a specific position.

2. One string can be obtained from the other by inserting/ deleting/ replacing a single character.

Hints

• Consider the different cases where two strings can be one edit distance apart: same length with one character difference, or one string is one character longer than the other.

• Traverse the strings simultaneously and keep track of the first encountered difference.

• After finding the first difference, check if the remaining characters in both strings are identical.

• Handle edge cases, such as empty strings or strings with the same content.

Approaches Explored

Approach 1: Brute Force

• Pros:
• Simple to understand and implement.
• Works for all cases.

• Cons:
• Time complexity of O(n^2), where n is the length of the longer string, as it involves generating and checking all possible edit combinations.
• Not efficient for large strings.

Approach 2: Optimized String Traversal

• Pros:
• Time complexity of O(n), where n is the length of the longer string.
• Space complexity of O(1), as it uses constant extra space.
• Efficient and optimized for most cases.

• Cons:
• Slightly more complex implementation compared to the brute force approach.

Finalized Approach

Executable Code

TheTechCruise.com Pyodide Terminal

class Solution:
    def isOneEditDistance(self, s: str, t: str) -> bool:
        i, ls, lt = 0, len(s), len(t)
        # Early return if the difference in length is more than 1, both strings are empty, or strings are equal
        if (abs(ls - lt) > 1) or (ls == 0 and lt == 0) or s == t: 
            return False
        # If one string is empty, the other must be exactly one character long to be true
        elif ls == 0 or lt == 0: 
            return True
        # Compare characters until the first difference is found
        for i in range(min(ls, lt)):
            if s[i] != t[i]:
                break
        else:
            i += 1
        # Handle the cases based on the length of strings and the position of difference
        if ls == lt: 
            return s[i+1:] == t[i+1:]
        elif lt > ls: 
            return s[i:] == t[i+1:]
        elif lt < ls: 
            return s[i+1:] == t[i:]
        return False

# Driver code to test the function with the given examples
def test_one_edit_distance():
    solution = Solution()
    test_cases = [
        ("ab", "acb"),   # True: Insert 'c' in "ab"
        ("", ""),        # False: Both strings are empty
        ("a", ""),       # True: Remove 'a' from "a"
        ("a", "A"),      # False: 'a' and 'A' are different (case-sensitive)
        ("a", "ac"),     # True: Append 'c' to "a"
        ("c", "c"),      # False: No changes needed (strings are the same)
        ("ba", "a"),     # True: Remove 'b' from "ba"
        ("ab", "acd")    # False: Requires two edits ('b' to 'c', append 'd')
    ]
    for s, t in test_cases:
        result = solution.isOneEditDistance(s, t)
        print(f"isOneEditDistance({s}, {t}): {result}")

# Execute the test function
test_one_edit_distance()

Code Analysis and Code Walkthrough

1. The function first initializes variables i, ls, and lt with values 0, len(s), and len(t), respectively.

2. It then checks for edge cases:
• If the absolute difference between the lengths of s and t is greater than 1, or both strings are empty, or both strings are equal, it returns False.
• If one of the strings is empty, it returns True.

3. If none of the edge cases are met, the function iterates through the strings s and t simultaneously using a for loop. It compares the characters at each position and breaks out of the loop as soon as it encounters the first difference. The loop counter i is updated to the index of the first difference.

4. After the loop, the function checks the following cases:
• If the lengths of s and t are equal, it checks if the remaining characters after the first difference are the same (i.e., s[i+1:] == t[i+1:]).
• If the length of s is less than t, it checks if remaining characters of s and t are equal after removal of t[i] i.e., s[i:] == t[i+1:]).
• If the length of s is greater than t, it checks if remaining characters of s and t are equal after removal of s[i] i.e., s[i+1:] == t[i:]).

5. If any of the above conditions are met, the function returns True, indicating that the strings are one edit distance apart. Otherwise, it returns False.

Example with Explanation

1. The function initializes i = 0, ls = 6, and lt = 6.

2. It checks the edge cases:
• The absolute difference between the lengths of s and t is 0, which is not greater than 1, so it proceeds.
• The strings are not equal, so it proceeds.
• Neither string is empty, so it proceeds.

3. The function iterates through the strings:
• At index 0, s[0] == 'r' and t[0] == 'r', so it continues.
• At index 1, s[1] == 'a' and t[1] == 'a', so it continues.
• At index 2, s[2] == 'n' and t[2] == 'n', so it continues.
• At index 3, s[3] == 'd' and t[3] == 's', so it breaks out of the loop with i = 3.

4. Since the lengths of s and t are the same (ls = 6 and lt = 6), the function checks if the substrings of s and t after the first difference are equal:
• s[i+1:] == t[i+1:] = "om" == "om" is True.

5. Since the condition is met, the function returns True, indicating that the strings "random" and "ransom" are one edit distance apart due to a single substitution of 'd' to 's'.

Explanation for other Test cases

1. ("ab", "acb"): Inserting 'c' between 'a' and 'b' makes them one edit apart. Returns True.

2. ("", ""): Both strings are empty; no edits needed. Returns False.

3. ("a", ""): Removing 'a' from "a" makes it empty, which is one edit. Returns True.

4. ("a", "A"): Changing 'a' to 'A' involves a substitution, but since they're case-sensitive and identical otherwise, it's an edit. Returns False because the strings are not the same.

5. ("a", "ac"): Appending 'c' to "a" results in "ac", which is one edit. Returns True.

6. ("c", "c"): No changes needed as the strings are identical. Returns False.

7. ("ba", "a"): Removing 'b' from "ba" leaves "a", which is one edit. Returns True.

8. ("ab", "acd"): Two edits are needed ('b' to 'c' and appending 'd'), so it's more than one edit distance. Returns False.

Discussion on Complexity

Conclusion