面试题 01.05. 一次编辑

Difficulty
Medium
Tags
动态规划
URL
https://leetcode.cn/problems/one-away-lcci/
Star
字符串有三种编辑操作:插入一个字符、删除一个字符或者替换一个字符。 给定两个字符串，编写一个函数判定它们是否只需要一次(或者零次)编辑。
示例 1:
输入:
first = "pale"
second = "ple"
输出: True
示例 2:
输入:
first = "pales"
second = "pal"
输出: False

法 1

思路
参考
🕍
72. 编辑距离 只不过本题是问能否只经过一次编辑，所以找到第一个不相同的字符位置 i， 然后向后判断三种情况：
  • 修改 字符 i first[i+1:] == second[i+1:]
  • 删除first字符 first[i] 或者在second[i] 处添加字符first[i], first[i+1:] == second[i:]
  • 删除 second 中字符 second[i], ... 同上
题解
class Solution:
    def oneEditAway(self, first: str, second: str) -> bool:
        if abs(len(first) - len(second)) > 1:
            return False

        for i in range(0, min(len(first), len(second))):
            # 找到第一个不相同的位置
            if first[i] != second[i]:
                return first[i+1:] == second[i+1:] or\
                        first[i+1:] == second[i:] or \
                        first[i:] == second[i+1:]
        return True