Wednesday, January 7, 2015

One Edit Distance -- Leetcode

Question:

Given two strings S and T, determine if they are both one edit distance apart.

Answer:

public class Solution {
    public boolean isOneEditDistance(String s, String t) {
       
        //consider all cases : 1.adj acj 2.acd abcd 3.abc abcd
       
        if(s.length() > t.length()){
            String tmp = t;
            t = s;
            s = tmp;
        }
        if(t.length() - s.length() >1)return false;   //to ensure t.length-s.length<=1
       
        boolean diffOne = false;
       
        for(int i=0,j=0; i< s.length(); ++i,++j){
            if(s.charAt(i) != t.charAt(j)){
               
                if(diffOne){
                    return false;
                }
               
                diffOne = true;
                if(t.length() > s.length()){
                    --i;
                }
            }
        }
       
        return diffOne || (t.length() > s.length());  
    }
}

No comments:

Post a Comment