面试题 01.05. 一次编辑

字符串有三种编辑操作:插入一个字符、删除一个字符或者替换一个字符。 给定两个字符串，编写一个函数判定它们是否只需要一次(或者零次)编辑。

示例 1:

输入:
first = "pale"
second = "ple"
输出: True

示例 2:

输入:
first = "pales"
second = "pal"
输出: False

PYthon 解答：
1.分情况讨论

class Solution:
    def oneEditAway(self, first: str, second: str) -> bool:
        if len(first) < len(second):
            first, second = second, first
        len1, len2 = len(first), len(second)
        if len1-len2 > 1:
            return False
        elif len1 == len2:
            count = 0
            for i in range(len1):
                if first[i] != second[i]:
                    count += 1
            if count > 1:
                return False
            else:
                return True
        else:
            i, j, k = 0, 0, 0
            while i < len(first):
                if first[i:i+1] == second[j:j+1]:
                    i += 1
                    j += 1
                else:
                    i += 1
                    k += 1
            if k == 1:
                return True
            else:
                return False

2.双指针

class Solution:
    def oneEditAway(self, first: str, second: str) -> bool:
        i, j, k = 0, len(first)-1, len(second)-1
        while i < len(first) and i < len(second) and first[i] == second[i]:
            i += 1
        while j >= 0 and k >= 0 and first[j] == second[k]:
            j -= 1
            k -= 1
        if j-i < 1 and k-i < 1:
            return True
        else:
            return False