一次编辑
- 难度：Medium
- 题目链接：https://leetcode-cn.com/problems/one-away-lcci/
题目描述
字符串有三种编辑操作:插入一个字符、删除一个字符或者替换一个字符。 给定两个字符串，编写一个函数判定它们是否只需要一次(或者零次)编辑。
示例 1:
输入: first = "pale" second = "ple" 输出: True
示例 2:
输入: first = "pales" second = "pal" 输出: False
解法：
此题可以先计算出编辑距离，然后判断编辑距离是否大于 1。但在此处，杀鸡就不用牛刀了。
如果字符串长度之差大于 1，一次编辑肯定不行。从头比较两个字符串，当字符不同时，有两种情况：
- 两个字符串长度差异为 0：这必然需要一个替换操作，此时增加编辑距离，指向两个字符串的指针均后移一位。
- 长度差异为 1：这必然需要替换或者插入操作，无论是哪种操作，都可以让较长的字符串的指针后移一位。
在遍历过程中，一旦发现编辑距离大于 1，则可立即返回。
class Solution {
public:
bool oneEditAway(string first, string second) {
if(first.size() < second.size()){
swap(first, second);
}
int len_diff = first.size() - second.size();
if(len_diff > 1){
return false;
}
int edit_distance = 0;
for (int i=0, j = 0; i < first.size(); i++, j++){
if(first[i] != second[j]){
edit_distance++;
if(edit_distance > 1){
return false;
}
if(len_diff == 1){
j--;
len_diff = 0;
}
}
}
return true;
}
};