面试题 01.05. 一次编辑

题目

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

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

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

题解

public boolean oneEditAway(String first, String second) {
    int firstLen = first.length(), secondLen = second.length();
    // 长度都小于1
    if (firstLen <= 1 && secondLen <= 1) {
        return true;
    }

    // 长度相差超过1
    if (Math.abs(firstLen - secondLen) > 1) {
        return false;
    }

    // 保证第一个字符串为较短的字符串
    if (firstLen > secondLen) {
        firstLen ^= secondLen;
        secondLen ^= firstLen;
        firstLen ^= secondLen;
        String temp = first;
        first = second;
        second = temp;
    }

    int i = 0, j = 0, flag = 1;
    // 双指针遍历
    while (i < firstLen && j < secondLen) {
        // 字符相同
        if (first.charAt(i) == second.charAt(j)) {
            i++;
            j++;
        } else {
            // 长度相同 则都进一位表示 替换字符操作
            if (firstLen == secondLen) {
                i++;
            }
            // 长度不同 跳过长字符串一次 这里可看做插入或删除字符操作
            j++;
            // 编辑次数减少
            flag--;
        }

        // 编辑次数大于1次
        if (flag < 0) {
            return false;
        }
    }

    return true;
}