# My CLEAR JAVA solution with explanation

• ``````/*
* 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;
}``````

• Thanks for the solution. You can get "Math.min(s.length(), t.length())" check to the outside of the for loop to improve performance.

• 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 no offense but his looks much better

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

• @lekzeey It's ok. Maybe this is an easier way to understand just for me. :)

• @Grain_In_Ear I agree. Final return should be "return s.length() != t.length();"

• 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.

1. sameDistance.
2. 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``````

• @GreenMonkey

The question is to determine if they are both one edit distance apart. If they are equal, they are NOT one edit distance apart.

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

• @ChengZhang

``````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.

• It seems s='abcd' and t='accc' is two edit distance (two replacements), but the code would return True. Who could correct me if I understand it wrong?

• Isn't replacing 1 char actually two edits? One edit to delete and one edit to add. The problem is ambiguous.

• @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 one-step edits could be stated explicitly: 1) change one character into another, 2) remove one character, 3) add one character

• Thanks @theredphone : )

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