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:
s to get t.s to get t.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 <= 10^40 <= t.length <= 10^4s and t consist of lower-case letters, upper-case letters and/or digits.
The description was taken from https://leetcode.com/problems/one-edit-distance/.
#O(Max(M,N)) Time, O(1) Space
class Solution:
def isOneEditDistance(self, s: str, t: str) -> bool:
if abs(len(s) - len(t)) > 1 or s == t:
return False
if len(s) + len(t) == 1:
return True
if len(s) > len(t):
return self.isOneEditDistance(t, s)
i, j = 0, 0 difference = False
while i < len(s) and j < len(t):
if s[i] != t[j]:
if difference:
return False
difference = True
if len(s) != len(t):
i -= 1
i += 1
j += 1
return TrueLet's take these use cases into account.
In order for us to see if we can delete or insert a character, the two string lengths would need to differ by one so that we could insert the character into the smaller string to become the larger string or vice versa with a deletion.
In order for us to replace a character, we would just disregard the two different characters within the iteration between both strings.
With that being said, since we are only checking for one differing character, utilizing two pointers, one for each string, is a good approach. If we were looking for more edits, we would probably have to apply some kind of dynamic programming solution.
We can get some base edge cases out of the way before traversing the strings which would falsify the inputs.
If the length of the two strings differs by more than one then we would have to either delete more than one character from the larger string or insert more than one character into the smaller string.
Similarly, if the strings are the same length then the edit distance would be zero.
If either of these cases is true, then we will return false.
if abs(len(s) - len(t)) > 1 or s == t:
return False
If the sum of both lengths equals one, then we would either delete a character from the non-null string or insert a character into the null string, in both scenarios the edit distance would be one so we will return true.
if len(s) + len(t) == 1:
return True
Otherwise, we will use our two-pointer approach.
This approach will work best if we have the first string be the smaller string, so if this is not the case then we will re-run the function with the inputs switched.
This will be explained later.
if len(s) > len(t):
return self.isOneEditDistance(t, s)
Let's set two pointers, i and j, for traversing strings s and t respectively.
i, j = 0, 0
We'll also create a flag for whether or not we have found a difference.
This is useful because once we find a differing character between the two input strings we will flip this flag. If we then find another difference later, and this flag is already flipped, that means we have at least two edits we would need to do and know to return false.
difference = False
Let's traverse the two strings.
while i < len(s) and j < len(t):
If we find a differing character, and we have already flipped the flag, we will return false.
if s[i] != t[j]:
if difference:
return False
Otherwise, we will flip the flag.
difference = True
Now, this is why we wanted to set s as the smaller string previously to make this portion of the code easier.
Deleting a character from a larger string and inserting a character into a smaller string to make two strings that differ by one character equal is the same use case.
If we have two differing lengths, and we wanted to see if we could insert into the smaller string or delete from the larger string, we could easily test for this by setting the pointer from the smaller string back.
Let's say, for example, we have "ab", and "acb".
We would find a differing character on the second iteration, "b" does not equal "c". By decrementing the first, smaller string's pointer, then once we increment both pointers at the end of the iteration, we would allow the same character in the smaller string to be compared to the next character in the larger string. This way, in the next iteration, we would compare "b" to "b".
The result would be that we would have to either delete "c" from the larger string or insert "b" into the smaller string, it would be the same use case.
if len(s) != len(t):
i -= 1
At the end of the iteration, we will increment both pointers.
i += 1
j += 1
If we have gotten to the end of both strings and never returned false then that means we can return true because have an edit distance of one.
We checked in the beginning that the strings weren't the same, so we know there is an edit distance of at least one.
If the string lengths were the same, and we didn't return false, then that means that our edit was a replacement of a single different character between the strings. If the string lengths were different, then that means we made an insertion on the smaller string to become the larger string or deletion on the larger string to become the smaller string.
return True