# One Edit Distance LeetCode Solution

Difficulty Level Medium

## Problem Statement

One Edit Distance LeetCode Solution – 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`.
```Input: s = "ab", t = "acb"
Output: true
Explanation: We can insert 'c' into s to get t.

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

## Explanation

We are given that there are three possibilities i.e 1. To replace a character 2. To Delete a Character 3. To add a Character

If we start iterating the strings s and t and for any index j where s[j]!=t[j] then these three possibilities can be countered as :

### Given s[ j ] != t[ j ]

A. If the length of s is equal to the length of t then we have no other option but to replace this character.

B. If s is longer than t then we have no other option but to delete this character in s.

C. If t is longer than s then we have no other option but to insert this character in s.

We can apply these conditions to get our result. ## Code

### C++ Code for One Edit Distance

```class Solution {
public:
bool isOneEditDistance(string s, string t) {
int diff = s.size()-t.size();
diff = diff>0? diff : -diff;

if (s == t || diff > 1) return false;

int i=0;
int j=0;

bool diffFound = false;
while (i<s.size() && j<t.size()) {
if (s[i] != t[j]) {
if (diffFound) return false;

if (s.size() >= t.size()) i++;
if (s.size() <= t.size()) j++;
diffFound = true;
} else {
i++;
j++;
}
}

return true;
}
};```

### Java Code for One Edit Distance

```class Solution {
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;
}
}```

### Python Code for One Edit Distance

```class Solution:
def isOneEditDistance(self, s, t):
"""
:type s: str
:type t: str
:rtype: bool
"""
if abs(len(s) - len(t)) > 1:
# If length of the two strings differs by more than one character,
# then the two strings cannot be one edit distance apart
return False

i = j = edits = 0
while i < len(s) and j < len(t):
if s[i] == t[j]:
# Characters match, move both i and j forward and continue the while loop
i, j = i + 1, j + 1
continue

# We reach here only when there is a mismatch
# Increment edits and return early if edits > 1
edits += 1
if edits > 1:
return False

# This reflects the three types of edits
if len(s) == len(t):
# Replace character in s
i, j = i + 1, j + 1
else:
if len(s) > len(t):
# Delete character from s
i += 1
else:
j += 1

if i < len(s) or j < len(t):
# Any left over characters (maximum of 1) will have to be deleted
edits += 1

# Return if input strings are exactly one edit distance away from each other
return edits == 1
```

## Complexity Analysis for One Edit Distance LeetCode Solution

### Time Complexity

O(N) since we iterate over the common length of two strings.

### Space Complexity

O(1) we don’t create any extra storage other than storing the size of strings and the result.

Translate »