Given two strings
true if they are both one edit distance apart, otherwise return
s is said to be one distance apart from a string
t if you can:
- Insert exactly one character into
- Delete exactly one character from
- Replace exactly one character of
swith a different character to get
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.
Input: s = "a", t = "" Output: true
Input: s = "", t = "A" Output: true
0 <= s.length <= 104
0 <= t.length <= 104
tconsist of lower-case letters, upper-case letters and/or digits.
In order to have only one edit distance, s and t should only have the same length or have one length difference. When their lengths are the same, s and t should have only one character difference. When their length differences are one, check if the longer string can remove one character to be the shorter string.
class Solution: def isOneEditDistance(self, s: str, t: str) -> bool: if s == t: return False if abs(len(s) - len(t)) > 1: return False if abs(len(s) - len(t)) == 0: diff_count = 0 for c1, c2 in zip(s, t): if c1 != c2: diff_count += 1 if diff_count > 1: return False else: return True else: long = s if len(s) > len(t) else t short = t if len(s) > len(t) else s for i in range(len(long)): after_delete = long[:i] + long[i+1:] if after_delete == short: return True return False
- Time Complexity: O(N).
- Space Complexity: O(N).
One Thought to “LeetCode 161. One Edit Distance”
Hey, I made an attempt to explain the intuitive approach to this problem using DP from recursive solution, you can check this out 😊