程序员面试金典 - 面试题 01.05. 一次编辑

题目难度: 中等

原题链接

今天继续更新程序员面试金典系列, 大家在公众号 算法精选 里回复 面试金典 就能看到该系列当前连载的所有文章了, 记得关注哦~

题目描述

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

示例 1:

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

示例 2:

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

题目思考

1. 两个字符串长度需要满足什么关系？

解决方案

思路

• 分析题目，只能有一次编辑，所以两个字符串长度的绝对值之差最多为 1
• 所以我们要先判断长度是否满足要求，满足的话使用双指针 + 一个 bool 变量 edited（标记是否已经编辑过）来遍历，遇到不匹配的字符时：
  • 如果 edited 是 true，直接返回 false，因为已经编辑过一次了；
  • 如果 edited 是 false，则根据长度关系决定是哪种编辑操作，并移动对应的下标，然后更新 edited 为 true。

复杂度

• 时间复杂度 O(N): 需要遍历两个字符串一遍
• 空间复杂度 O(1): 只使用了几个变量

代码

class Solution:
    def oneEditAway(self, first: str, second: str) -> bool:
        # 判断长度差+双指针, 分三种情况
        if abs(len(first) - len(second)) > 1:
            return False
        i, j = 0, 0
        edited = False
        while i < len(first) and j < len(second):
            if first[i] == second[j]:
                i += 1
                j += 1
            else:
                if edited:
                    return False
                if len(first) < len(second):
                    # first需要插入一个字符, 所以second下标后移一位, 代表插入字符和second[j]匹配
                    j += 1
                elif len(first) > len(second):
                    # first需要删除一个字符, 所以first下标后移一位
                    i += 1
                else:
                    # first需要改变当前字符first[i]=>second[j], 所以两个下标都后移一位
                    i += 1
                    j += 1
                edited = True
        return True

大家可以在下面这些地方找到我~😊

我的知乎专栏

我的头条号

我的 CSDN

我的 Leetcode

我的牛客网博客

我的公众号: 算法精选, 欢迎大家扫码关注~😊