One Edit Distance

题目描述

Given two strings S and T, determine if they are both one edit distance apart.

解题方法

这道题目和edit distance是相关的，one edit有三种可能的操作

• Insert a character
• Delete a character

• Replace a character

• 首先是长度差距不能超过１

• 如果长度差距是１的花，insert和delete其实是一样的，就是长的那个string　delete一个字符
• 长度相等的时候，它们相对应位置字符不同的个数不能多于１

Solution

class Solution(object):
    def isOneEditDistance(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: bool
        """
        lengthS = len(s)
        lengthT = len(t)

        diff = abs(lengthS - lengthT)

        if diff > 1:
            return False
        elif diff == 1:
            if lengthS > lengthT:
                for i in range(lengthS):
                    tmp = s[0:i] + s[i+1:]
                    if tmp == t:
                        return True
            else:
                for i in range(lengthT):
                    tmp = t[0:i] + t[i+1:]
                    if tmp == s:
                        return True
            return False
        else:
            if s == t:
                return False
            diffNum = 0
            for i in range(lengthS):
                if s[i] != t[i]:
                    if diffNum == 0:
                        diffNum += 1
                    else:
                        return False
            return True

Reference