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