一次编辑

题目

题目来源：力扣（LeetCode）

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

示例 1:

输入:
first = “pale”
second = “ple”
输出: True

示例 2:

输入:
first = “pales”
second = “pal”
输出: False

思路分析

双指针

1. 双指针遍历，⽤⼀个标记位记录是否编辑过。
2. 当出现不相等的字符，就给它⼀次编辑的机会，后⾯再出现不相等就返回 false 。
3. 编辑策略：如果两字符串⻓度相等，就⽤替换是最⼩编辑；不相等的话，⻓度⻓的字符串指针⾛⼀ 步就可以了，相当于字符串⻓的那个删除⼀个字符。
4. 时间复杂度是 O(N) , 空间复杂度是O(1)。因为双指针是同时动的，⽽且两字符⻓度肯定是相等的或 者只差1才需要⽐较。

/**
 * @param {string} first
 * @param {string} second
 * @return {boolean}
 */
var oneEditAway = function (first, second) {
  // 因为只有一次编辑的机会，如果两个字符串长度相差大于1，直接返回false
  if (Math.abs(first.length - second.length) > 1) return false;
  let i = 0;
  let j = 0;
  let edit = false;
  while (i < first.length && j < second.length) {
    // 两个字符串从前往后开始遍历，如果字符一样就继续比较下一个
    if (first.charAt(i) === second.charAt(j)) {
      i++;
      j++;
    } else {
      // 当出现不相等的字符，给予它⼀次编辑的机会，后⾯再出现不相等就返回 false 。
      if (!edit) {
        if (first.length === second.length) {
          // 如果两字符串⻓度相等，就⽤替换是最⼩编辑
          i++;
          j++;
        } else if (first.length < second.length) {
          // 不相等的话，⻓度⻓的字符串指针⾛⼀步就可以了，相当于字符串⻓的那个删除⼀个字符。
          j++;
        } else {
          i++;
        }
        edit = true;
      } else {
        return false;
      }
    }
  }
  return true;
};