/*
* There're 3 possibilities to satisfy one edit distance apart:
*
* 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
*/
public boolean isOneEditDistance(String s, String 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()) // s has the same length as t, so the only possibility is replacing one char in s and t
return s.substring(i + 1).equals(t.substring(i + 1));
else if (s.length() < t.length()) // t is longer than s, so the only possibility is deleting one char from t
return s.substring(i).equals(t.substring(i + 1));
else // s is longer than t, so the only possibility is deleting one char from s
return t.substring(i).equals(s.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;
}
My CLEAR JAVA solution with explanation


@can12 said in My CLEAR JAVA solution with explanation:
Thanks for the solution. You can get "Math.min(s.length(), t.length())" check to the outside of the for loop to improve performance.
I think it's ok. Compiler will optimize this.

@can12 compiler definitely optimizes that. Brilliant solution, way better than the one in CTCI.

Very smart! It's much clear to figure out how to handle when we find the first different char.
Here is the current version inspired by yours! Thanks for sharing!public boolean isOneEditDistance(String s, String t) { int m = s.length(), n = t.length(); if (Math.abs(m  n) > 1) return false; for (int i = 0; i < Math.min(m, n); i++) { if (s.charAt(i) == t.charAt(i)) continue; if (m == n) return s.substring(i + 1).equals(t.substring(i + 1)); if (m > n) return s.substring(i + 1).equals(t.substring(i)); else return s.substring(i).equals(t.substring(i + 1)); } return m != n; /* Only last char different. eg."abcd" "abc". Rule out equal case "abc" "abc" */ }


@cdai Hi, I think you actually need to check if s and t are equal, or it won't handle these cases.



Just for the sake of cleaner code, we can always make sure "s" is shorter than "t". Then we just need to handle two cases.
 sameDistance.
 s is shorter than t by 1 char.
public class Solution { public boolean isOneEditDistance(String s, String t) { int n1 = s.length(), n2 = t.length(); if (n2 < n1) { return isOneEditDistance(t, s); } boolean sameDist = (n1 == n2); for (int i = 0; i < n1; i++) { if (s.charAt(i) != t.charAt(i)) { if (sameDist) { return s.substring(i + 1).equals(t.substring(i + 1)); } else { return s.substring(i).equals(t.substring(i + 1)); } } } return (n1 + 1 == n2)  (n2 + 1 == n1); } }

public boolean isOneEditDistance(String s, String t) { int m = s.length(), n = t.length(); if(m < n) return isOneEditDistance(t, s); if(m == n){ boolean isOneEdit = false; for(int i=0;i<m;i++){ if(s.charAt(i) != t.charAt(i)){ if(!isOneEdit){ isOneEdit = true; } else return false; } } return isOneEdit; } else { for(int i=0;i<n;i++){ if(s.charAt(i) != t.charAt(i)) return s.substring(i+1).equals(t.substring(i)); } return m  1 == n; } }wo

@Grain_In_Ear Thanks for pointing out! The length m and n are compared before return, I think it's ok, right?

I like your approach. I made some slight modifications.
public class Solution { public boolean isOneEditDistance(String s, String t) { // From @ChengZhang: //There're 3 possibilities to satisfy one edit distance apart: // 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 int sLength = s.length(); int tLength = t.length(); if ((s.equals(t))  (Math.abs(sLength  tLength) > 1)) { return false; // by definition, if they are the same, they are not exactly ONE edit distance away, or if greater than 1 char different not possible } if (sLength > tLength) { // convert case 2 to case 3 return isOneEditDistance(t, s); // want the first string to be shorter, to handle cases 2 and 3 } boolean sameDist = (sLength == tLength); // used to check for case 1 for (int i = 0; i < sLength; i++) { if (s.charAt(i) != t.charAt(i)) { // when first different char hit if (sameDist) { // if same distance, compare remaining substrings, case 1 return s.substring(i + 1).equals(t.substring(i + 1)); } else { // if not, t is always longer at this point, case 3, part 1 return s.substring(i).equals(t.substring(i + 1)); } } } return true; // t has one extra char that s doesn't have, case 3 part 2 for last char } }

@Matt.X.Zhao I like the idea of converting one of the three possibilities into one of the remaining two, so there are now only two cases two handle: if they are the same length with one different char and the case where t is longer and at most one char can be deleted.

@aaron86 The code doesn't just check equal length but at the first and only first time a difference is encountered for equal length strings, it then compares the substrings of the remaining. If they are the same, true; else, false. So for s='abcd' and t='accc', when it gets to the second index it sees s(1) = 'b' != 'c' = t(1) and then compares the remaining substrings, and since 'cd' != 'cc' it returns false.

@shogen It is implied that a substitution, ie turning an 'a' into a 'b', is one edit. The onestep edits could be stated explicitly: 1) change one character into another, 2) remove one character, 3) add one character
