面试题01.05.一次编辑

链接：面试题01.05.一次编辑
难度：Medium
标签：双指针、字符串
简介：字符串有三种编辑操作:插入一个字符、删除一个字符或者替换一个字符。 给定两个字符串，编写一个函数判定它们是否只需要一次(或者零次)编辑。

题解 1 - typescript

• 编辑时间：2021-10-16
• 执行用时：92ms
• 内存消耗：39.9MB
• 编程语言：typescript
• 解法介绍：遍历。

function oneEditAway(first: string, second: string): boolean {
  if (first === second) return true;
  if (first.length < second.length) [first, second] = [second, first];
  const l1 = first.length;
  const l2 = second.length;
  const minus = Math.abs(l1 - l2);
  if (minus > 1) return false;
  else if (minus === 0) {
    for (let i = 0, j = 0; i < l1; i++) {
      if (first[i] !== second[i]) {
        if (j === 1) return false;
        j++;
      }
    }
    return true;
  } else {
    let idxFirst = -1;
    let idxLast = -1;
    for (let i = 0, l = Math.min(l1, l2); i < l; i++) {
      if (first[i] !== second[i]) {
        idxFirst = i;
        break;
      }
    }
    if (idxFirst === -1) return true;
    for (let i1 = l1 - 1, i2 = l2 - 1; i1 >= 0 && i2 >= 0; i1--, i2--) {
      if (first[i1] !== second[i2]) {
        idxLast = i1;
        break;
      }
    }
    if (idxLast === -1) return true;
    return idxFirst === idxLast;
  }
}

题解 2 - cpp

• 编辑时间：2022-05-13
• 执行用时：52ms
• 内存消耗：12MB
• 编程语言：cpp
• 解法介绍：遍历。

class Solution {
   public:
    bool oneEditAway(string first, string second) {
        int n1 = first.size(), n2 = second.size();
        int i1 = 0, i2 = 0, cnt = 0;
        for (; i1 < n1 && i2 < n2; i1++, i2++) {
            if (first[i1] == second[i2]) continue;
            if (cnt == 1) return false;
            cnt++;
            if (i1 + 1 < n1 && first[i1 + 1] == second[i2])
                i1++;
            else if (i2 + 1 < n2 && first[i1] == second[i2 + 1])
                i2++;
        }
        if (cnt == 0) return abs(n1 - n2) <= 1;
        return i1 == n1 && i2 == n2 && cnt <= 1;
    }
};