Recursive Java solution with explanation


  • 0
    Y

    public class Solution {
    /**
    * There is three possibilities in this question for s and t:
    * 1. Replace current character in s or t to be the same. eg: s = aBc, t = aDc
    * Note this can only happen when s.length() == t.length()
    * 2. Delete current character in s. eg: s = aBcd, t = acd
    * Note this is the same with insert a character in t. And this can only happen when s.length() > t.length()
    * 3. Delete current character in t. eg: s = acd, t = aBcd
    * Note this is the same with insert a character in s. And this can only happen when t.length() > s.length()
    *
    * This question actually asks for judging if s and t are exactly one distance away, that is, is s and t are the same, then we return false.
    *
    * Thus we can get the following algorithm:
    */
    public boolean isOneEditDistance(String s, String t) {
    if (s == null || t == null || Math.abs(s.length() - t.length()) >= 2) return false;

        return helper(s, 0, t, 0, 0);
    }
    
    private boolean helper(String s, int i, String t, int j, int count) {
        if (count > 1) return false;
        if (i < s.length() && j < t.length()) {
            if (s.charAt(i) == t.charAt(j)) {
                return helper(s, i + 1, t, j + 1, count);
            } else {
                if (s.length() == t.length()) {
                    return helper(s, i + 1, t, j + 1, count + 1);
                }
                if (s.length() < t.length()) {
                    return helper(s, i, t, j + 1, count + 1);
                }
                if (s.length() > t.length()) {
                    return helper(s, i + 1, t, j, count + 1);
                }
            }
        }
        
        if (s.length() == t.length()) return count == 1;
        return Math.abs(s.length() - t.length()) == 1;
    }
    

    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.