medium, Array/String
Question
確定兩個字符串S和T是否是單一edit distance
Solution
假設(shè)len(S) = n, len(T) = m
- | n – m |>1, False
- 假設(shè)m<=n總是成立（otherwise, 交換S和T即可）
- m == n愈犹，如果可以修改一個字符達(dá)到S==T，True
- m<n, 插入一個字符達(dá)到S==T, True
Example
i. Modify operation – Modify a character to X in S.
S = “abcde”
T = “abXde”
ii. Insert operation – X was inserted before a character in S.
S = “abcde”
T = “abcXde”
iii. Append operation – X was appended at the end of S.
S = “abcde”
T = “abcdeX”
class Solution(object):
def isOneEditDistance(self, s,t):
"""
:type s: str
:type t: str
:rtype: bool
"""
m, n = len(s), len(t)
if m > n:
s, t = t, s
if n-m>1:
return False
i = 0
shift = n-m
while i < m and s[i] == t[i]:
i+=1
if i==m: return shift > 0
if shift == 0: i+=1
while i<m and s[i] == t[i+shift]:
i+=1
return i==m
