One Edit Distance

Problem

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

Solution

public class Solution {
    public boolean isOneEditDistance(String s, String t) {
        int sLen = s.length(), tLen = t.length();
        if (Math.abs(sLen - tLen) >= 2) return false;
        for (int i = 0; i < Math.min(sLen, tLen); i++) {
            if (s.charAt(i) != t.charAt(i)) {
                if (sLen == tLen) return s.substring(i + 1).equals(t.substring(i + 1)); //Change char
                if (sLen > tLen) return s.substring(i + 1).equals(t.substring(i)); //Delete s
                return s.substring(i).equals(t.substring(i + 1)); //Add s (Delete t)
            }
        } 
        return Math.abs(sLen - tLen) == 1; //Must check this 
    }
}

Analysis

There are only three situations for One Edit Distance, which is to replace, add, or remove
Therefore, we just need to move to the first different place of two given strings then decide specific situation based on s.length() and t.length()
1) They have equal length, we can ignore only one different character s.substring(i+1).equals(t.substring(i+1))
2) s has longer length, we can ignore that different character from s s.substring(i+1).equals(t.substring(i))
3) s has shorter length, we can ignore that different character from t s.substring(i).equals(t.substring(i+1))
At the end, we must check s.len and t.len has exact one distance, cause we use i < Math.min(sLen, tLen)
Notice that two same strings are not One Edit Distance

results matching ""

    No results matching ""