161. One Edit Distance

Given two strings S and T, determine if they are both one edit distance apart.



Solution:

If the lengths of two strings are equal, we check if there's only one difference.

If the lengths of one string is 1 character larger than the other. If they are one edit distance, we can find the index i which differs, and substring(i + 1) of the longer one and substring(i) of the shorter one should equal.

If the length difference of two strings is larger than 1, they cannot have only one edit distance.

The time complexity is O(n).



Code:

public class Solution {
    public boolean isOneEditDistance(String s, String t) {
        if (Math.abs(s.length() - t.length()) > 1) {
            return false;
        }
        if (s.length() == t.length()) {
            return replaceOne(s, t);
        }
        if (s.length() > t.length()) {
            return removeOne(s, t);
        }
        return removeOne(t, s);
    }
    public boolean removeOne(String s, String t){
        for (int i = 0; i < s.length() - 1; i++){
            if (s.charAt(i) != t.charAt(i)){
                return s.substring(i + 1).equals(t.substring(i));
            }
        }
        return true;
    }
    public boolean replaceOne(String s,String t){
        int diff = 0;
        for (int i = 0; i < s.length(); i++){
            if (s.charAt(i) != t.charAt(i)) {
                diff++;
            }
        }
        return diff == 1;
    }
}