161. One Edit Distance
Given two stringss andt, determine if they are both one edit distance apart.
There are 3 possiblities to satisify one edit distance apart:
- Insert a character into s to get t
- Delete a character from s _to get t_
- Replace a character of s _to get t_
Input: s = "ab", t = "acb" Output: true Explanation: We can insert 'c' into s to get t.
Input:s = "cab", t = "ad" Output: false Explanation: We cannot get t from s by only one step.
Input:s = "1203", t = "1213" Output: true Explanation: We can replace '0' with '1' to get t.
- Compare the string until first no equal char meet:
- return a[i+1:] == b[i:] # for deleteing ith element in a (assume a is longer than b)
- return a[i+1:] == b[i+1] # for replacing one to the other
- if two strings are equal in min(len(a),len(b)) return whether the distance is within 1 # for insert shorter one the last element from the longer one at the end
class Solution(object): def isOneEditDistance(self, s, t): """ :type s: str :type t: str :rtype: bool """ m, n = len(s), len(t) for i in range(min(m,n)): if s[i] != t[i]: if m > n: return s[i+1:] == t[i:] # delete s[i] elif m == n: return s[i+1:] == t[i+1:] # replace else: return s[i:] == t[i+1:] # delete t[i] return abs(m - n) == 1