2.4 One Edit Distance 161
Description
Given two strings S and T, determine if they are both one edit distance apart.
Hint
one edit distance apart : 3 possibilties
* 1) Replace 1 char: s: a B c t: a D c
* 2) Delete 1 char from s: s: a D b c t: a b c
* 3) Delete 1 char from t s: a b c t: a D b c
Method
compare from head to tail if meet a different char
check the remain string
take care of one situation whether their are the same
Time & Space
O(n)
Code
public boolean isOneEditDistance(String s, String t) {
if (s == null || t == null){
return s == t;
}
for (int i = 0; i < Math.min(s.length(), t.length()); i++){
if (s.charAt(i) != t.charAt(i)){
if (s.length() == t.length()){
return s.substring(i + 1).equals(t.substring(i + 1));
} else if (s.length() > t.length()){
return s.substring(i + 1).equals(t.substring(i));
} else {
return s.substring(i).equals(t.substring(i + 1));
}
}
}
//All previous chars are the same, the only possibility is deleting the end char in the longer one of s and t
return Math.abs(s.length() - t.length()) == 1;
}