[Leetcode] One Edit Distance

[Problem Link]

If you’ve solved the edit distance dynamic programming problem, this problem should be straightforward.

1. Make sure to return false if both strings are equal. The problem asks us to return true only if they’re one edit distance apart! Proceed if they’re unequal.
2. Use two pointers set at the end of each string. Find the ‘first’ character thats a mismatch. Keep in mind to stop if either of the pointers reach the end. Even if you exhaust one of the strings and have remaining characters left in the other, its still a mismatch!
3. Once we’ve found ‘one’ mismatch, we need to simply check if inserting, deleting or replacing a character gives us an equal string. For checking this we create a checkEquals() method.
4. checkEquals() method simply checks if two (sub) strings are exactly equal! We’ll pass both the strings and ending indexes i and j to this method. Return whatever checkEquals() returns.

class Solution {
    public boolean isOneEditDistance(String s, String t) {
 
        if ( s.equals(t) )
            return false;
 
        int i = s.length() - 1;
        int j = t.length() - 1;
 
        while ( i >= 0 && j >= 0 ) {
            if ( s.charAt(i) != t.charAt(j) )
                break;
            i--; j--;
        }
 
        // check if insert, delete or replace returns a valid string!
        return checkEquals(s, t, i-1, j) || 
                checkEquals(s, t, i, j-1) || 
                    checkEquals(s, t, i-1, j-1);
    }
 
    public boolean checkEquals(String s, String t, int i, int j) {
        if ( i != j )
            return false;
 
        while ( i >= 0 ) {
            if ( s.charAt(i) != t.charAt(j) )
                return false;
            i--; j--;
        }
 
        return true;
    }
}