My CLEAR JAVA solution with explanation


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

  • 0
    C

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


  • 2
    B

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


  • 0
    L

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


  • 2

    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" */
        }
    

  • 0
    L

    @cdai no offense but his looks much better


  • 0
    G

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


  • 0

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


  • 0
    G

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


  • 3
    M

    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);
        }
    }
    

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

  • 0
    M

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


  • 0

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


  • 0
    T

    @ChengZhang

    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
        }
    }
    

  • 0
    T

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


  • 0
    A

    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?


  • 0
    S

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


  • 0
    T

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


  • 0
    T

    @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


  • 0
    A

    Thanks @theredphone : )


Log in to reply
 

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