面试题 01.05. 一次编辑

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

示例 1:

输入: 
first = "pale"
second = "ple"
输出: True
1
2
3
4

示例 2:

输入: 
first = "pales"
second = "pal"
输出: False
1
2
3
4

Python实现

如果字符不同的下标个数不超过 1，则符合一次编辑或零次编辑。这样的话遍历找到第一个不同的字符，然后判断其右边的字符串是否相同来判断是否只能一次编辑。

class Solution:
    def oneEditAway(self, first: str, second: str) -> bool:
        m, n = len(first), len(second)
        if m<n:
            return self.oneEditAway(second,first)
        if m-n>1:
            return False
        for i,(x,y) in enumerate(zip(first,second)):
            if x!=y:
                if m==n:
                    return first[i+1:]==second[i+1:]
                else:
                    return first[i+1:]==second[i:]
        return True
1
2
3
4
5
6
7
8
9
10
11
12
13
14