跳转至

面试题 01.05. 一次编辑 #

问题描述#

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

示例 1:
输入: 
first = "pale"
second = "ple"
输出: True
示例 2:
输入: 
first = "pales"
second = "pal"
输出: False

解题思路#

两个字符串的长度最多相差 1。
如果两个字符串的长度相等，则最多只能有一个字符不同。
如果长度相差为 1，则长度较长的字符串去掉与短的字符串第一个不同的字符后，得到的字符串应该与短的字符串相同。

class Solution:
    def oneEditAway(self, first: str, second: str) -> bool:
        if len(first) < len(second):
            first, second = second, first
        if len(first) - len(second) > 1:
            return False

        for i, c in enumerate(second):
            if c != first[i]:
                return (first[i+1:] == second[i+1:]) or (first[i+1:] == second[i:])
        return True