0161._One_Edit_Distance.md

161. One Edit Distance

难度: Medium

刷题内容

原题连接

• https://leetcode.com/problems/one-edit-distance/

内容描述

Given two strings s and t, determine if they are both one edit distance apart.

Note: 

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
Example 1:

Input: s = "ab", t = "acb"
Output: true
Explanation: We can insert 'c' into s to get t.
Example 2:

Input: s = "cab", t = "ad"
Output: false
Explanation: We cannot get t from s by only one step.
Example 3:

Input: s = "1203", t = "1213"
Output: true
Explanation: We can replace '0' with '1' to get t.

解题方案

思路 1 - 时间复杂度: O(N)- 空间复杂度: O(N)******

开始写的特别复杂，利用Counter 来考虑每种情况，

class Solution:
    def isOneEditDistance(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: bool
        """
        def subtract(cnt1, cnt2):
            res = {}
            for ele in cnt1:
                if ele not in cnt2:
                    res[ele] = cnt1[ele]
                else:
                    res[ele] = cnt1[ele] - cnt2[ele]
            return res
        
        def diffEqualOne(s, t):
            if len(s) != len(t):
                return False
            diff = 0
            for i in range(len(s)):
                if s[i] != t[i]:
                    diff += 1
            return diff == 1
        
        def checkDeleteOrInsert(s, t):
            if len(s) < len(t):
                s, t = t, s
            if len(s) == 1 and not t:
                return True
            l, r = 0, 0
            diff = 0
            while l < len(s) and r < len(t):
                if s[l] != t[r]:
                    diff += 1
                    l += 1
                    if diff > 1:
                        return False
                l += 1
                r += 1
            return diff == 1 or l == len(s) - 1
        
        tmp = collections.Counter(s+t)
        cnt_s = subtract(tmp, collections.Counter(t))
        cnt_t = subtract(tmp, collections.Counter(s))
        cnt = subtract(cnt_s, cnt_t)
        edit = 0
        for ele in cnt:
            if cnt[ele] == 0:
                continue
            else:
                if abs(cnt[ele]) != 1:
                    return False
                else:
                    edit += 1
        return (edit == 1 and checkDeleteOrInsert(s, t)) or (edit == 2 and diffEqualOne(s, t))

思路 2 - 时间复杂度: O(N)- 空间复杂度: O(N)******

可以直接将其变化成应该有的样子后再看s和t是否一样

beats 95.92%

class Solution:
    def isOneEditDistance(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: bool
        """
        if s == t:
            return False 
        if abs(len(s) - len(t)) > 1:
            return False
        for i in range(min(len(s), len(t))):
            if s[i] != t[i]:
                if len(s) == len(t):
                    s = s[:i] + t[i] + s[i+1:] # replacement
                elif len(t) > len(s):
                    s = s[:i] + t[i] + s[i:]   # insertion
                else:
                    s = s[:i] + s[i+1:]        # deletion
                break
        # 后面两个是为了 checking edge case for s ="a", t = ""
        return s == t or s == t[:-1] or s[:-1] == t 

思路 3 - 时间复杂度: O(N)- 空间复杂度: O(N)******

找到第一个不一样的字符之后，再根据s和t哪个更长，然后比较剩余的部分是否相等即可

class Solution:
    def isOneEditDistance(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: bool
        """
        if s == t:
            return False
        i = 0
        while  i < min(len(s), len(t)) and s[i] == t[i]:
            i += 1
        return s[i + (len(s) >= len(t)):] == t[i + (len(t) >= len(s)):]