【双指针】一次编辑

题目

面试题 01.05. 一次编辑

---

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

示例 1:

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

示例 2:

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

解题

方法一：双指针

思路

先对比两个字符串的长度，如果长度差大于 2 直接判否，返回 false。

确保 first 的长度比 second 短（后面会用到），否则交换。

使用两个指针(fstIdx, secIdx)同时从 0 开始扫描两个字符串，并维护一个 editCnt 用于记录修改次数：

• 如果两个指针指向的字符相同，两指针后移，直接进行下一次遍历
• 两字符不相同时，必会发生修改，故先把修改次数加一，如果修改次数超过一直接返回 false：
  • 如果两字符串长度相等，说明只能替换一个字符，两指针后移
  • 如果两字符串长度不等，说明要删除一个字符，因为前面保证了 first 的长度必比 second 短，则fstIdx 不动，secIdx 后移即代表删除了一个 second 中的字符

如果遍历完成，则 first 一定可以在经过一次以内的编辑变为 second，返回 true。

代码

class Solution {
    public boolean oneEditAway(String first, String second) {
        int fstLen = first.length(), secLen = second.length();
        if (Math.abs(first.length() - second.length()) > 1) return false;
        if (fstLen > secLen) return oneEditAway(second, first);
        int editCnt = 0;
        for (int fstIdx = 0, secIdx = 0; fstIdx < fstLen && secIdx < secLen;) {
            char fstChar = first.charAt(fstIdx), secChar = second.charAt(secIdx);
            if (fstChar == secChar) {
                fstIdx++;
                secIdx++;
            } else {
                if (++editCnt > 1) return false;
                if (fstLen == secLen) {
                    fstIdx++;
                    secIdx++;
                } else secIdx++;
            }
        }
        return true;
    }
}