题目

字符串有三种编辑操作：插入一个字符、删除一个字符或者替换一个字符。给定两个字符串，编写一个函数判断它们是否只需要一次（或者零次）编辑。
image.png

思路

  • 长度相差超过1位，返回False
  • 长度相差1位（判断是否有插入、删除），双指针
    • 第一次碰到字符不一样，短字符串指针不动，长字符串指针+1；第二次碰到则返回False
  • 长度相等（判断是否有替换操作）
    • 第一次碰到字符不一样，短字符串指针+1，长字符串指针+1
      1. class Solution:
      2. def oneEditAway(self, first: str, second: str) -> bool:
      3.    if first == second: return True
      4.    # len(first) > len(second)
      5.    if len(first) < len(second):
      6.        first, second = second, first
      7.    if len(first) - len(second) > 1:
      8.        return False
      9.    i, j = 0, 0
      10.    flag = False
      11.    times = 0
      12.    if len(first) == len(second):
      13.        while i < len(first) and j < len(second):
      14.            if first[i] != second[j] and times < 1:
      15.                flag = not flag # 布尔值取反
      16.                times += 1
      17.            elif first[i] != second[j] and times >= 1:
      18.                return False
      19.            i += 1
      20.            j += 1
      21.        return flag
      22.    else:
      23.        # 相差1
      24.        while i < len(first) and j < len(second):
      25.            if first[i] != second[j] and times < 1:
      26.                flag = not flag
      27.                times += 1
      28.                i += 1
      29.            elif first[i] == second[j]:
      30.                i += 1
      31.                j += 1
      32.            else:
      33.                # times == 1
      34.                return False
      35.        return True

还可以用动态规划来解答。

  • 留坑，回头来填