0161. One Edit Distance

https://leetcode.com/problems/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.

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.

ac1: iterative

class Solution {
    public boolean isOneEditDistance(String s, String t) {
        // edge cases
        if (s.length() == 0 && t.length() == 0
           || s.equals(t)) return false;

        // length diff
        boolean lenDiffFlag = false;
        int lenDiff = s.length() - t.length();
        if (Math.abs(lenDiff) > 1) return false;
        if (Math.abs(lenDiff) == 1) lenDiffFlag = true;

        String shrt = lenDiff > 0 ? t : s;
        String lng = lenDiff > 0 ? s : t;

        // char walk
        int diff = 0;
        for (int i = 0, j = 0; i < shrt.length() && j < lng.length(); i++, j++) {
            if (shrt.charAt(i) != lng.charAt(j)) {
                diff++;
                if (lenDiffFlag) {
                    i--;
                    lenDiffFlag = false;
                } // shorter one step back one char
            }

            if (diff > 1) return false;
        }

        // return
        return true;
    }
}
// edit: 1) insert/delete -> length diff 1, 2) change, length equal, one char diff

ac2: compare substring

class Solution {
    public boolean isOneEditDistance(String s, String t) {
        // s for short, t for long;
        if (s.length() > t.length()) return isOneEditDistance(t, s);

        // length diff
        int lenS = s.length(), lenT = t.length();
        if (lenT - lenS > 1) return false;

        // walk
        for (int i = 0; i < lenS; i++) {
            if (s.charAt(i) != t.charAt(i)) {
                return s.substring(i+1).equals(t.substring(i+1))
                    || s.substring(i).equals(t.substring(i+1));
            }
        }

        return lenT > lenS; // this one is pretty counterintuitive...
    }
}

class Solution {
    public boolean isOneEditDistance(String s, String t) {
        // edge cases
        if (s == null || t == null || s.equals(t) 
            || Math.abs(s.length() - t.length()) > 1) 
            return false;

        // short long
        String shrt = s.length() > t.length() ? t : s;
        String lng = s.length() > t.length() ? s : t;

        for (int i = 0; i < shrt.length(); i++) {
            if (shrt.charAt(i) != lng.charAt(i)) {
                return shrt.substring(i+1).equals(lng.substring(i+1))  // same length
                    || shrt.substring(i).equals(lng.substring(i+1));  // long string has one more char
            }
        }

        return true;
    }
}