字符串有三种编辑操作:插入一个英文字符、删除一个英文字符或者替换一个英文字符。 给定两个字符串,编写一个函数判定它们是否只需要一次(或者零次)编辑。
输入:
first = "pale"
second = "ple"
输出: True
输入:
first = "pales"
second = "pal"
输出: False
刚拿到题目,第一时间直接想到统计词频...用一个unordered_map来存一下,遍历第一个字符串将字符++,遍历第二个字符串将字符--,如果字符的value是0就将其erase掉,最后判断剩余的字符数,后来发现题目里面有排列顺序的问题...无奈放弃 :(
改用双指针!
直接上代码!
bool oneEditAway(string ff, string ss) {
int m = ff.size(), n = ss.size();
//相差大于1 直接see goodbye;
if (abs(m - n) > 1)
{
return false;
}
//新增了呀,比我大了呀,那就你们交换下位置吧!
if(n == m + 1)
{
return oneEditAway(ss, ff);
}
int i = 0, j = 0;
int diff = 0;
//开始遍历,双指针冲冲冲
while (i < m && j < n)
{
//找到不同的了
if(ff[i] != ss[j])
{
diff++;
if(diff >= 2)
{
return false;
}
//first 比 second 长了一点
//pale ple a != l 所以 second 原地等待一下下
if(m > n)
{
j--;
}
}
j++;
i++;
}
return true;
}
灰常滴简单哇~
Q.E.D.