161. One Edit Distance (Medium)

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

注：one edit distance: converting word1 to word2 only needs one step. You have the following 3 operations permitted on a word:

a) Insert a character

b) Delete a character

c) Replace a character

Solution 1: Iterative O(n); O(1)

    /**
     * Solution 1: Iterative O(n); O(1)
     * Compare the lengths of two strings, always put the shorter string as the first parameter.
     * If the difference of their lengths are larger than 1, return false.
     * Traverse the shorter string to find a different char.
     * If found and they are of same length, the rest of them should be the same.
     * If found and they are of different length, the rest of shorter string, including that char,
     * should be the same as the rest of longer string, excluding that char.
     * If all chars are the same, it can only be the last character in longer string.
     * Return true iff longer string is one character longer.
     */
    public boolean isOneEditDistance(String s, String t) {
        int m = s.length();
        int n = t.length();
        if (Math.abs(m - n) > 1) {
            return false;
        }

        if (m > n) { //always put the shorter string as the first parameter.
            return isOneEditDistance(t, s);
        }
        for (int i = 0; i < m; i++) {
            if (s.charAt(i) == t.charAt(i)) {
                continue;
            }

            if (m == n) { //if return true, mean Replacing a character is OK. abc, acc
                return s.substring(i + 1).equals(t.substring(i + 1));
            }
            //if return true, mean Deleting a character is OK. ac, abc
            return s.substring(i).equals(t.substring(i + 1)); 
        }
        return m != n; //cannot return false since the corner case can be only the last char is different. a, ab
    }