161. One Edit Distance

Posted on | Edited on | Views:

https://leetcode.com/problems/one-edit-distance/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/*
class Solution {
    public boolean isOneEditDistance(String s, String t) {
        int len_s=s.length();
        int len_t=t.length();
        if(Math.abs(len_s-len_t)>1) return false;
        if(len_s==len_t){
            int i=0,j=0,cnt=0;
            while(i<len_s){if(s.charAt(i++)!=t.charAt(j++)) cnt++;}
            if(cnt==0||cnt>1||len_s==0) return false;
        }else if(len_s>len_t){
            int i=0,j=0,cnt=0;
            while(i<len_s&&j<len_t&&len_t>0){
                if(s.charAt(i)==t.charAt(j)) {i++;j++;}
                else {i++;cnt++;}
            }
            if(cnt>1) return false;
        }else{
            int i=0,j=0,cnt=0;
            while(i<len_s&&j<len_t&&len_s>0){
                if(s.charAt(i)==t.charAt(j)) {i++;j++;}
                else {j++;cnt++;}
            }
            if(cnt>1) return false;
        }
        return true;
    }
}*/
class Solution {
    public boolean isOneEditDistance(String s, String t) {
        int len_s=s.length();
        int len_t=t.length();
        if(len_s<len_t) return isOneEditDistance(t,s);// guarantee that len_s > len_t
        if(len_s-len_t>1) return false;
        if(len_s==len_t){
            int i=0,j=0,cnt=0;
            while(i<len_s){if(s.charAt(i++)!=t.charAt(j++)) cnt++;}
            if(cnt==0||cnt>1||len_s==0) return false;
        }else{
            int i=0,j=0,cnt=0;
            while(i<len_s&&j<len_t&&len_t>0){
                if(s.charAt(i)==t.charAt(j)) {i++;j++;}
                else {i++;cnt++;}
            }
            if(cnt>1) return false;
        }
        return true;
    }
}

LeetCode Solution Explanation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/*
 * 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%