161. One Edit Distance

Description

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.

Constraints

• 0 <= s.length <= 104

• 0 <= t.length <= 104

• s and t consist of lower-case letters, upper-case letters and/or digits.

Approach

Links

• GeeksforGeeks

• Leetcode

• ProgramCreek

• YouTube

Examples

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

Solutions

Solution 1

/**
 * Time complexity : O(N) in the worst case when string lengths are close 
 *    enough abs(ns - nt) <= 1, where N is a number of characters in the 
 *    longest string. O(1) in the best case when abs(ns - nt) > 1.
 * Space complexity : O(N) because strings are immutable in Python and Java 
 *    and to create substring costs O(N) space.
 */

class Solution {
    public boolean isOneEditDistance(String s, String t) {
        int ns = s.length();
        int nt = t.length();

        // Ensure that s is shorter than t.
        if (ns > nt)
            return isOneEditDistance(t, s);

        // The strings are NOT one edit away distance  
        // if the length diff is more than 1.
        if (nt - ns > 1)
            return false;

        for (int i = 0; i < ns; i++)
            if (s.charAt(i) != t.charAt(i))
                // if strings have the same length
                if (ns == nt)
                    return s.substring(i + 1).equals(t.substring(i + 1));
                // if strings have different lengths
                else
                    return s.substring(i).equals(t.substring(i + 1));

        // If there is no diffs on ns distance
        // the strings are one edit away only if
        // t has one more character. 
        return (ns + 1 == nt);
    }
}

Solution 2

/**
 * Time complexity : O(N)
 * Space complexity : O(1)
 */

class Solution {
    public boolean isOneEditDistance(String s, String t) {
        if(s == null || t == null) return false;
        
        int sLen = s.length(), tLen = t.length();
        
        if(sLen == 0 && tLen == 0 || Math.abs(sLen-tLen) > 1) return false;
        
        int i = 0, j = 0;
        
        int diff = 0;
        while(i < sLen && j < tLen) {
            if(s.charAt(i) == t.charAt(j)) {
                i++;
                j++;
            } else {
                diff++;
                if(diff > 1) return false;
                if(sLen > tLen) {
                    i++;
                } else if(sLen < tLen) {
                    j++;
                } else {
                    i++;
                    j++;
                }
            }
        }
        
        if(i < sLen || j < tLen) diff++;
        
        return diff == 1;
    }
}

Follow up