1.题目描述
字符串有三种编辑操作:插入一个字符、删除一个字符或者替换一个字符。 给定两个字符串，编写一个函数判定它们是否只需要一次(或者零次)编辑。
示例 1:
输入:
first = "pale"
second = "ple"
输出: True
示例 2:
输入:
first = "pales"
second = "pal"
输出: False
2.思路
2.1 代码
使用双指针进行解答，firstPtr 指向 first 字符串，secondPtr 指向 second 字符串。当 first 字符串和 second 字符串长度大于 1 时所需操作不符合题目，直接返回 false。
使用 op 统计当前操作次数，当 firstPtr 和 secondPtr 所指向的字符相等时，firstPtr 和 secondPtr 自增指向下一个字符。当 firstPtr 和 secondPtr 指向字符不相同时，有以下几种情况：
- 当 op 等于 1 时，此时说明之前已经操作过一次了，而当前字符串又不相同还需要再操作一次，不符合题意，返回 false
- 如果 first 长度大于 second 长度，此时需要对 first 字符删减或者对 second 增加字符，此时只需要将 firstPtr 加一，让 firstPtr 指向下一位表示上一位已处理完毕
- 如果 first 长度小于 second 长度，此时需要对 second 字符删减或者对 first 增加字符，此时只需要将 secondPtr 加一，让 secondPtr 指向下一位表示上一位已处理完毕
- 如果 first 长度和 second 长度相等，此时只需要替换，firstPtr 和 secondPtr 同时增加 1 ，指向下一位。以上三种情况因为包含增加、删除、替换操作，因此均会使 op 操作加一。
代码如下：
class Solution {
public boolean oneEditAway(String first, String second) {
if (Math.abs(first.length() - second.length()) > 1) {
return false;
}
int firstPtr = 0;
int secondPtr = 0;
int op = 0;
while (firstPtr < first.length() && secondPtr < second.length()) {
if (first.charAt(firstPtr) == second.charAt(secondPtr)) {
firstPtr++;
secondPtr++;
} else {
if (op == 1) {
return false;
}
if (first.length() > second.length()) {
firstPtr++;
} else if (first.length() < second.length()) {
secondPtr++;
} else {
firstPtr++;
secondPtr++;
}
op++;
}
}
return true;
}
}
2.2 测试结果
通过测试
测试结果
3.总结
- 使用双指针进行解答
- 如果指针指向字符不同，需要考虑 first 长度大于、小于、等于 second 长度三种情况
