面试题01.05. 一次编辑

面试题01.05. 一次编辑

题目：字符串有三种编辑 *** 作，插入一个字符、删除一个字符或者替换一个字符。给定两个字符串，编写一个函数判定它们是否只需要一次（或者零次）编辑。

示例1：

输入：

first = "pale"

second = "ple"

输出：True

示例2：

输入：

first = "pales"

second = "pal"

输出：False

 1. 思考

先分析允许进行的 *** 作：

1. 插入一个字符：当两个字符串长度只相差1的时候可能满足，稍短的字符串将某个字符往后的字符数组平移一位后，剩余字符与稍长的字符串一致。

2. 删除一个字符：两个字符串长度只相差1的时候可能满足，同时删除一个字符可以看作是插入一个字符的相反 *** 作。即删除一个字符是指稍长字符串删除一个字符得到稍短字符串，也可以看作是稍短字符串插入一个字符得到稍长字符串。

3. 替换一个字符：两个字符串长度相同时可能满足，两个字符串只有唯一一个索引位的字符不一致。

在了解所有一次编辑 *** 作场景的本质后，我们就可以根据两个字符串长度间的关系，分别判断是否满足对应场景条件，比如两个字符串first和second。

1. len(first) == len(second)

 判断first和second是否只有0个或者1个索引位的字符不相同。

2. len(first) + 1 == len(second)

first字符串的长度比second少1，判断是否first添加一个字符就可以与second一致。

3. len(first) == len(second) + 1

first字符串的长度比second多1，判断是否second添加一个字符就可以与first一致。

4. 其他情况不可能仅一次编辑使first与second一致

其中场景1中判断first和second是否仅有不超过1个索引位的字符不相同很简单，遍历字符串，记录不相同的字符总数即可。

场景2和场景3中判断first是否插入一个字符就可以和second一致，观察上图可以发现，如果first与second存在首个索引位不一致后，当前first索引位字符直接与second的后一个索引位字符比较，如果后续字符都一致，说明满足first插入一个字符就与second一致的可能。

假定len(first) + 1 == len(second)，实现代码如下：

// first是否可以插入一个字符和second一致
public boolean oneInsert(String first, String second) {
    // index1记录当前判断的first索引位
    int index1 = 0;
    // index2记录当前判断的second索引位
    int index2 = 0;
    // 遍历所有字符
    while (index1 < first.length() && index2 < second.length()) {
        if (first.charAt(index1) == second.charAt(index2)) {
            // 当两个字符索引位字符一致时，后移索引
            index1++;
            index2++;
        }
        else {
            // 当两个字符索引位字符不一致时，先判断是否是第一次不一致
            // 如果不是第一次不一致说明second后移一位后仍有不一致字符
            // 即无法将first插入一个字符与second一致
            if (index1 != index2) {
                return false;
            }
            // 第一次不一致，second索引后移一位
            index2++;
        }
    }
    return true;
}

 2. 代码实现

根据上面分析思路，代码实现如下：

public boolean oneEditAway(String first, String second) {
    if (first == null || second == null) {
        return false;
    }
    if (first.length() == second.length()) {
        // 字符数相同，需要考虑相等（零次编辑）和一次修改字符两种场景
        if (oneReplace(first, second)) {
            return true;
        }
    }
    else if (first.length() + 1 == second.length()) {
        // first字符个数比second少一个，考虑first添加一个字符和second一致
        if (oneInsert(first, second)) {
            return true;
        }
    }
    else if (first.length() == second.length() + 1) {
        // first字符个数比second多一个，考虑second添加一个字符和first一致
        if (oneInsert(second, first)) {
            return true;
        }
    }
    // 其他情况不可能一次编辑让first和second一致
    return false;
}
// first和second是否只有不超过1个字符不同
private boolean oneReplace(String first, String second) {
    int diffNum = 0;
    for (int i = 0; i < first.length(); i++) {
        if (first.charAt(i) != second.charAt(i)) {
            diffNum++;
        }
    }
    return diffNum <= 1;
}
// first添加一个字符与second一致
private boolean oneInsert(String first, String second) {
    int index1 = 0;
    int index2 = 0;
    while (index1 < first.length() && index2 < second.length()) {
        if (first.charAt(index1) == second.charAt(index2)) {
            index1++;
            index2++;
        }
        else {
            if (index1 != index2) {
                return false;
            }
            index2++;
        }
    }
    return true;
}