# One Edit Distance

Given two strings `s` and `t`, return `true` if they are both one edit distance apart, otherwise return `false`.

A string `s` is said to be one distance apart from a string `t` if you can:

• Insert exactly one character into `s` to get `t`.
• Delete exactly one character from `s` to get `t`.
• Replace exactly one character of `s` with a different character to get `t`.

Example 1:

```Input: s = "ab", t = "acb"
Output: true
Explanation: We can insert 'c' into s to get t.
```

Example 2:

```Input: s = "", t = ""
Output: false
Explanation: We cannot get t from s by only one step.
```

Example 3:

```Input: s = "a", t = ""
Output: true
```

Example 4:

```Input: s = "", t = "A"
Output: true
```

Constraints:

• `0 <= s.length <= 104`
• `0 <= t.length <= 104`
• `s` and `t` consist of lower-case letters, upper-case letters and/or digits.

First of all, let’s ensure that the string lengths are not too far from each other. If the length difference is 2 or more characters, then `s` and `t` couldn’t be one edit away strings.

Now what if there is a different character so that `s[i] != t[i]`.

• If the strings are of the same length, all next characters should be equal to keep one edit away distance. To verify it, one has to compare the substrings of `s` and `t` both starting from the `i + 1`th character.
• If `t` is one character longer than `s`, the additional character `t[i]` should be the only difference between both strings. To verify it, one has to compare a substring of `s` starting from the `i`th character and a substring of `t` starting from the `i + 1`th character.

Implementation

```class Solution {
public boolean isOneEditDistance(String s, String t) {

int m = s.length();
int n = t.length();
int k = Math.min(m, n);
for(int i = 0 ; i < k ; i++){
char sc = s.charAt(i);
char tc = t.charAt(i);
if( sc != tc){
if(m == n){
// 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( m > n){
// s is longer than t, so the only possibility
// is deleting one char from s
return s.substring(i+1).equals(t.substring(i));
}else{
// t is longer than s, so the only possibility
// is deleting one char from t
return t.substring(i+1).equals(s.substring(i));
}
}
}
// 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(m-n) == 1;
}
}
```

Complexity Analysis

• Time Complexity : `O(N)` in the worst case when string lengths are close enough `abs(len_of_s - len_of_t) <= 1`, where `N` is a number of characters in the longest string. `O(1) `in the best case when `abslen_of_s - len_of_t) > 1`.
• Space Complexity : `O(N)` because strings are immutable in Java and to create substring costs `O(N)` space.

Categories: String

Tagged as: , ,