One Edit Distance

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.

Example 1:

Input: s = "ab", t = "acb"
Output: true
Explanation: We can insert 'c' into s to get t.

Example 2:

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

Example 3:

Input: s = "a", t = ""
Output: true

Example 4:

Input: s = "", t = "A"
Output: true

Constraints:

  • 0 <= s.length <= 104
  • 0 <= t.length <= 104
  • s and t consist of lower-case letters, upper-case letters and/or digits.

First of all, let’s ensure that the string lengths are not too far from each other. If the length difference is 2 or more characters, then s and t couldn’t be one edit away strings.

Now what if there is a different character so that s[i] != t[i].

  • If the strings are of the same length, all next characters should be equal to keep one edit away distance. To verify it, one has to compare the substrings of s and t both starting from the i + 1th character.
  • If t is one character longer than s, the additional character t[i] should be the only difference between both strings. To verify it, one has to compare a substring of s starting from the ith character and a substring of t starting from the i + 1th character.
One Edit Distance

Implementation

class Solution {
    public boolean isOneEditDistance(String s, String t) {
        
        int m = s.length();
        int n = t.length();
        int k = Math.min(m, n);
        for(int i = 0 ; i < k ; i++){
            char sc = s.charAt(i);
            char tc = t.charAt(i);
            if( sc != tc){
                if(m == n){
                    // 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( m > n){ 
                    // s is longer than t, so the only possibility 
                    // is deleting one char from s
                    return s.substring(i+1).equals(t.substring(i));
                }else{
                    // t is longer than s, so the only possibility 
                    // is deleting one char from t
                    return t.substring(i+1).equals(s.substring(i));
                }
            }
        }
        // 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(m-n) == 1;
    }
}

Complexity Analysis

  • Time Complexity : O(N) in the worst case when string lengths are close enough abs(len_of_s - len_of_t) <= 1, where N is a number of characters in the longest string. O(1) in the best case when abslen_of_s - len_of_t) > 1.
  • Space Complexity : O(N) because strings are immutable in Java and to create substring costs O(N) space.

Categories: String

Tagged as: , ,

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s