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 长度三种情况