161. One Edit Distance

Published on September 16, 2023

Question

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.

Algorithm

This question is basic, you just loop each character, if they are different, then that is the editing point, mark edited, and continue going, if there is other dieting point then return false since we have more than one editing point; or there is no editing point that's still a false.

One thing to notice is that you need to be careful after loop, the short is done but the longer string isn't. There may be one more character to loop if their length are not equal. In such situation, the add/delete edit point is the last character. Don't forget this.

There is another recursive solution(I don't think that's my idea thought it's in my submission records.)

Code1

class Solution {
    public boolean isOneEditDistance(String s, String t) {
        int ns = s.length();
        int nt = t.length();
        
        if (ns > nt) {
            return isOneEditDistance(t, s);
        }
        
        if (nt - ns > 1) {
            return false;
        }
        
        for (int i = 0; i < ns; i++) {
            if (s.charAt(i) != t.charAt(i)) {
                if (ns == nt) {
                    return s.substring(i + 1).equals(t.substring(i + 1));
                } else {
                    return s.substring(i).equals(t.substring(i + 1));
                }
            }
        }
        return (ns + 1 == nt);
    }
}

Code2

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