161. One Edit Distance


Problem Description

The problem provides two strings, s and t, and asks us to determine if they are one edit distance apart. Being "one edit distance apart" means that there is exactly one simple edit that can transform one string into the other. This edit can be one of the following types:

  • Inserting exactly one character into s to get t.
  • Deleting exactly one character from s to get t.
  • Replacing exactly one character in s with a different character to get t.

To solve this problem, we need to carefully compare the two strings and verify if they differ by exactly one of the aforementioned operations or, in contrast, they are either identical or differ by more than one operation.

Intuition

The solution exploits the fact that if two strings are one edit distance apart, their lengths must differ by at most one. If the lengths differ by more than one, more than one edit is required, which violates the problem constraints. Therefore, the solution begins by comparing the lengths of s and t:

  1. If s is shorter than t, swap them to ensure that we only have one case to handle for insertions or deletions (the case where s is longer than or equal to t).

  2. If the difference in lengths is greater than one, return False immediately.

  3. Iterate over the shorter string and compare the characters at each index with the corresponding characters in the longer string.

  • The moment a mismatch is encountered, there are two scenarios to consider based on the length of the strings:

    • If s and t are of the same length, the only possible edit is to replace the mismatching character in s with the character from t. Check if the substrings of s and t after the mismatch indices are identical.

    • If s is longer than t by one, the only possible edit is a deletion. Check if the substring of s after the mismatch index plus one is identical to the substring of t after the index of the mismatch.

  • If no mismatch is found and the loop completes, one last check is needed: if s is longer than t by one character, then the last character of s could be the extra character, satisfying the condition for being one edit distance apart.

In conclusion, this solution systematically eliminates scenarios that would require more than one edit and carefully checks for the one allowed edit between the given strings.

Learn more about Two Pointers patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece:

Consider the classic dynamic programming of longest increasing subsequence:

Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

For example, the length of LIS for [50, 3, 10, 7, 40, 80] is 4 and LIS is [3, 7, 40, 80].

What is the recurrence relation?

Solution Approach

The implementation of the solution provided uses a straightforward approach that does not rely on any additional data structures or complex patterns. Let's take a closer look at the algorithm:

  1. Check Lengths and Swap: The function begins by making sure that s is the longer string. If it's not, it calls itself with the strings reversed.

    1if len(s) < len(t):
    2   return self.isOneEditDistance(t, s)

    This optimizes the code by allowing us to only think about two scenarios (instead of three): replacing a character or deleting a character from s.

  2. Check Length Difference: If the length of s is more than one character longer than t, they cannot be one edit apart, so the function returns False.

    1if m - n > 1:
    2    return False
  3. Iterate and Compare Characters: The next step involves iterating over the shorter string t and checking character by character to find any differences.

    1for i, c in enumerate(t):
    2    if c != s[i]:

    As soon as a difference is found, the function moves to the next step.

  4. Check Possible One Edit Scenarios: Upon encountering a mismatch, there are now two cases to consider:

    • For strings of the same length (m == n), a replacement might be the one edit. The function checks if the substrings after the different characters are the same.

      1return s[i + 1 :] == t[i + 1 :]
    • If s is longer by one character (m == n + 1), it indicates a possible deletion. The code checks if the substring of s beyond the next index is the same as the substring of t from the current index.

      1return s[i + 1 :] == t[i:]
  5. Final Check for Deletion at the End: If the for loop finishes without finding any mismatches, the function finally checks if s is exactly one character longer than t, which would imply the possibility of the one edit being a deletion at the end.

    1return m == n + 1

Throughout its process, this approach relies purely on the properties of strings and their indices. It uses string slicing to compare substrings and eliminate the need for additional operations. This makes for an efficient approach both in terms of space, not requiring any additional storage, and in terms of time, as it can short-circuit and exit as soon as it finds the strings are not one edit distance apart.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What is the best way of checking if an element exists in a sorted array once in terms of time complexity? Select the best that applies.

Example Walkthrough

Let's illustrate the solution approach using a small example. Consider two strings s = "cat" and t = "cut". We want to determine whether they are one edit distance apart using the above solution approach.

  1. Check Lengths and Swap: Since the length of s is equal to t, no swapping occurs.

    1if len(s) < len(t):
    2   return self.isOneEditDistance(t, s)
  2. Check Length Difference: The lengths of s and t are the same, so this condition is not triggered.

    1if m - n > 1:
    2    return False
  3. Iterate and Compare Characters: We iterate over each character in t and compare it with the corresponding character in s.

    1for i, c in enumerate(t):
    2    if c != s[i]:

    The loop encounters a mismatch at index 1: 'a' in s is different from 'u' in t.

  4. Check Possible One Edit Scenarios: Since s and t are of the same length, we check if replacing the second character in s with the corresponding character in t would make the strings equal.

    1  return s[i + 1 :] == t[i + 1 :]

    This returns True as s[2:] ('t') is identical to t[2:] ('t'), indicating that replacing 'a' with 'u' in s results in t.

So, s and t are indeed one edit distance apart as we only need to replace one character ('a' with 'u') to transform s into t.

Not Sure What to Study? Take the 2-min Quiz:

Which technique can we use to find the middle of a linked list?

Python Solution

1class Solution:
2    def isOneEditDistance(self, s: str, t: str) -> bool:
3        # If s is shorter than t, swap them to make sure s is longer or equal to t
4        # This helps in reducing further checks
5        if len(s) < len(t):
6            return self.isOneEditDistance(t, s)
7
8        # Extract lengths of both strings.
9        len_s, len_t = len(s), len(t)
10
11        # There cannot be a one edit distance if the length difference is more than 1
12        if len_s - len_t > 1:
13            return False
14
15        # Iterate through both strings
16        for idx in range(len_t):
17            # If the characters at current position are different,
18            # It must either be a replace operation when lengths are same,
19            # Or it must be an insert operation when lengths are different.
20            if s[idx] != t[idx]:
21                if len_s == len_t:
22                    # The remainder of the strings after this character should
23                    # be the same if it is a replace operation.
24                    return s[idx + 1:] == t[idx + 1:]
25                else:
26                    # In case of insert operation, the remainder of the longer string
27                    # starting from the next character should be the same as the 
28                    # rest of shorter string starting from current character.
29                    return s[idx + 1:] == t[idx:]
30
31        # If all previous chars are same, the only possibility for one edit distance
32        # is when the longer string has one extra character at the end.
33        return len_s == len_t + 1
34

Java Solution

1class Solution {
2
3    public boolean isOneEditDistance(String s, String t) {
4        int lengthS = s.length(), lengthT = t.length();
5
6        // Ensure s is the longer string.
7        if (lengthS < lengthT) {
8            return isOneEditDistance(t, s);
9        }
10
11        // If the length difference is more than 1, it's not one edit distance.
12        if (lengthS - lengthT > 1) {
13            return false;
14        }
15
16        // Check each character to see if there's a discrepancy.
17        for (int i = 0; i < lengthT; ++i) {
18            if (s.charAt(i) != t.charAt(i)) {
19                // If the lengths are the same, the rest of the strings must be equal after this character.
20                if (lengthS == lengthT) {
21                    return s.substring(i + 1).equals(t.substring(i + 1));
22                }
23                // If the lengths are not the same, the rest of the longer string must be equal to the rest of the shorter string after this character.
24                return s.substring(i + 1).equals(t.substring(i));
25            }
26        }
27
28        // Covers the case where there is one extra character at the end of the longer string.
29        return lengthS == lengthT + 1;
30    }
31}
32

C++ Solution

1class Solution {
2public:
3    // Check if string 's' can be converted to string 't' with exactly one edit
4    bool isOneEditDistance(string s, string t) {
5        int lenS = s.length(), lenT = t.length(); // Use more descriptive variable names
6
7        // Guarantee that 's' is not shorter than 't'
8        if (lenS < lenT) return isOneEditDistance(t, s);
9
10        // If the strings differ in length by more than 1, it can't be one edit
11        if (lenS - lenT > 1) return false;
12
13        // Iterate through characters in both strings
14        for (int i = 0; i < lenT; ++i) {
15            // If characters don't match, check the types of possible one edit
16            if (s[i] != t[i]) {
17                // If lengths are the same, check for replace operation
18                if (lenS == lenT) return s.substr(i + 1) == t.substr(i + 1);
19                // If lengths differ, check for insert operation
20                return s.substr(i + 1) == t.substr(i);
21            }
22        }
23
24        // If all previous characters matched, check for append operation
25        return lenS == lenT + 1;
26    }
27};
28

Typescript Solution

1// Check if string 's' can be converted to string 't' with exactly one edit
2function isOneEditDistance(s: string, t: string): boolean {
3    let lengthS = s.length; // Length of string 's'
4    let lengthT = t.length; // Length of string 't'
5
6    // Ensure 's' is not shorter than 't'
7    if (lengthS < lengthT) return isOneEditDistance(t, s);
8
9    // If the lengths differ by more than 1, it can't be a single edit
10    if (lengthS - lengthT > 1) return false;
11
12    // Iterate through characters in both strings
13    for (let i = 0; i < lengthT; i++) {
14        // If characters don't match, check the types of possible one edit
15        if (s[i] !== t[i]) {
16            // If lengths are the same, check for replace operation
17            if (lengthS === lengthT) return s.substring(i + 1) === t.substring(i + 1);
18            // If lengths differ, check for insert operation
19            return s.substring(i + 1) === t.substring(i);
20        }
21    }
22
23    // If all previous characters matched, it might be an append operation
24    return lengthS === lengthT + 1;
25}
26
Fast Track Your Learning with Our Quick Skills Quiz:

Which algorithm is best for finding the shortest distance between two points in an unweighted graph?

Time and Space Complexity

Time Complexity

The time complexity of the given code is O(N) where N is the length of the shorter string between s and t. This complexity arises from the fact that we iterate through each character of the shorter string at most once, comparing it with the corresponding character of the longer string. In the worst case, if all characters up to the last are the same, we perform N comparisons.

Space Complexity

The space complexity of the code is O(1). No additional space is required that scales with the input size. The only extra space used is for a few variables to store the lengths of strings and for indices, which does not depend on the size of the input strings.

Learn more about how to find time and space complexity quickly.


Recommended Readings


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫