One Edit Distance

medium, Array/String

Question

确定两个字符串S和T是否是单一edit distance

Solution

假设len(S) = n, len(T) = m

1. | n – m |>1, False
2. 假设m<=n总是成立（otherwise, 交换S和T即可）
3. m == n，如果可以修改一个字符达到S==T，True
4. m<n, 插入一个字符达到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