面试题 01.05. 一次编辑

题目

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

示例 1:

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

示例 2:

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/one-away-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

首先，两个字符串长度相差大于1肯定返回false。

然后，同时遍历两个字符串，记录不同的字符数，遇到不同的字符时，根据两个字符串的长度关系进行下一步操作：

如果长度相等，那么接着遍历；

如果不同，说明一长一短，且相差1，如果满足题意，必须是删除长度较长的字符串当前字符后，两个串应该相同，那么跳过该字符，后面的字符应该完全相同。实现上，因为每一轮都会两个指针++，那么将较短字符串的指针—，然后再一起++，剩下需要比较的字符个数就一样多了。如果出现不同的字符数大于1，返回false，否则返回true。

代码

class Solution {
    public boolean oneEditAway(String first, String second) {
        int n = first.length();
        int m = second.length();
        if (n - m > 1 || m - n > 1) {
            return false;
        }
        int diff = 0;
        int i = 0;
        int j = 0;
        while (i < n && j < m) {
            if (first.charAt(i) != second.charAt(j)) {
                diff++;
                if (diff >= 2) {
                    return false;
                }
                if (n > m) {
                    j--;
                }
                if (m > n) {
                    i--;
                }
            }
            i++;
            j++;
        }
        return true;
    }
}