One Edit Distance LeetCode Solution

Difficulty Level Medium
Frequently asked in Amazon Apple Facebook Google Microsoft Snapchat Twitter Uber YandexViews 3076

Problem Statement

One Edit Distance LeetCode Solution – Given two strings s and t, return true if they are both one edit distance apart, otherwise return false.

A string s is said to be one distance apart from a string t if you can:

  • Insert exactly one character into s to get t.
  • Delete exactly one character from s to get t.
  • Replace exactly one character of s with a different character to get t.
Input: s = "ab", t = "acb"
Output: true
Explanation: We can insert 'c' into s to get t.

Input: s = "", t = ""
Output: false
Explanation: We cannot get t from s by only one step.

Explanation

We are given that there are three possibilities i.e 1. To replace a character 2. To Delete a Character 3. To add a Character

If we start iterating the strings s and t and for any index j where s[j]!=t[j] then these three possibilities can be countered as :

Given s[ j ] != t[ j ]

A. If the length of s is equal to the length of t then we have no other option but to replace this character.

B. If s is longer than t then we have no other option but to delete this character in s.

C. If t is longer than s then we have no other option but to insert this character in s.

We can apply these conditions to get our result.

One Edit Distance LeetCode Solution

Code

C++ Code for One Edit Distance

class Solution {
public:
    bool isOneEditDistance(string s, string t) {
       int diff = s.size()-t.size();
       diff = diff>0? diff : -diff;
       
       if (s == t || diff > 1) return false;
       
       int i=0; 
       int j=0; 
       
       bool diffFound = false;
       while (i<s.size() && j<t.size()) {
           if (s[i] != t[j]) {
               if (diffFound) return false;
               
               if (s.size() >= t.size()) i++;
               if (s.size() <= t.size()) j++;
               diffFound = true;
           } else {
               i++;
               j++;
           }
       }
       
       return true;
    }
};

Java Code for One Edit Distance

class Solution {
   public boolean isOneEditDistance(String s, String t) {
    for (int i = 0; i < Math.min(s.length(), t.length()); i++) { 
      if (s.charAt(i) != t.charAt(i)) {
        if (s.length() == t.length()) // s has the same length as t, so the only possibility is replacing one char in s and t
          return s.substring(i + 1).equals(t.substring(i + 1));
      else if (s.length() < t.length()) // t is longer than s, so the only possibility is deleting one char from t
        return s.substring(i).equals(t.substring(i + 1));            
      else // s is longer than t, so the only possibility is deleting one char from s
        return t.substring(i).equals(s.substring(i + 1));
      }
    }       
    //All previous chars are the same, the only possibility is deleting the end char in the longer one of s and t 
    return Math.abs(s.length() - t.length()) == 1;        
}
}

Python Code for One Edit Distance

class Solution:
    def isOneEditDistance(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: bool
        """
        if abs(len(s) - len(t)) > 1:
            # If length of the two strings differs by more than one character,
            # then the two strings cannot be one edit distance apart
            return False

        i = j = edits = 0
        while i < len(s) and j < len(t):
            if s[i] == t[j]:
                # Characters match, move both i and j forward and continue the while loop
                i, j = i + 1, j + 1
                continue

            # We reach here only when there is a mismatch
            # Increment edits and return early if edits > 1
            edits += 1
            if edits > 1:
                return False

            # This reflects the three types of edits
            if len(s) == len(t):
                # Replace character in s
                i, j = i + 1, j + 1
            else:
                if len(s) > len(t):
                    # Delete character from s
                    i += 1
                else:
                    # Add character to s
                    j += 1

        if i < len(s) or j < len(t):
            # Any left over characters (maximum of 1) will have to be deleted
            edits += 1

        # Return if input strings are exactly one edit distance away from each other
        return edits == 1

Complexity Analysis for One Edit Distance LeetCode Solution

Time Complexity

O(N) since we iterate over the common length of two strings.

Space Complexity

O(1) we don’t create any extra storage other than storing the size of strings and the result.

Reference: https://algodaily.com/lessons/using-the-two-pointer-technique

Translate »