2ms Java solution with explanation


  • 0
    C
    public class Solution {
        public boolean isOneEditDistance(String s, String t) {
            
            // this removes difference between character insertion and removal
            if(s.length()>t.length()) return isOneEditDistance(t, s);
            
            // If difference in lengths is greater than 1, it cannot be oneEditDistance
            if(t.length()-s.length()>1) return false;   
            
            int p1 = 0, p2 = 0;
            int len1 = s.length();
            int len2 = t.length();
            
            while(p1<len1 && p2<len2){
                if (s.charAt(p1)!=t.charAt(p2)){
                    
                    // If the length is different rest of string s including this character should match since unmatched character
                    // in string t would account for one edit (i.e.deletion) distance.
                    // If on the other hand if length is same, current character in string s would account for one edit 
                    // (i.e. substitution distance, and hence rest of the string needs to be matched.
                    String suffix = (len1!=len2)? s.substring(p1): s.substring(p1+1);
                    return suffix.equals(t.substring(p2+1));
                } else {
                   p1++;
                   p2++;
                }
            }
            
            // code reaching here implies, prefixes of two strings are same. Now if length is equal it would imply 
            // zero edit distance and hence should return false.
            return len1!=len2;
        }
    }
    

Log in to reply
 

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