0 题目来源

力扣《程序员面试金典》

1 涉及到的知识点

字符串操作

2 题目描述

字符串有三种编辑操作:插入一个字符、删除一个字符或者替换一个字符。 给定两个字符串，编写一个函数判定它们是否只需要一次(或者零次)编辑。

3 样例

示例 1:
输入:
first = “pale”
second = “ple”
输出: True

示例 2:
输入:
first = “pales”
second = “pal”
输出: False

4 思路

根据两个字符串长度的差值，分情况讨论。
如果两个字符串长度差值大于1，则肯定不是一次编辑。
如果两个字符串完全一致，则属于零次编辑，返回true。
如果两个字符串长度差值为1，则说明属于插入或删除的情况。
如果两个字符串长度相等，则说明属于替换的情况。

对于插入和删除的情况，我们对两个字符串进行同步遍历，如果对应字符不相等，则cnt计数加一，然后较短字符串不动，较长字符串移到下一位继续比较。如果cnt>1，则返回false；如果整个遍历过程中cnt一直小于等于1，则返回true。
对于替换的情况，对两个字符串的相应位置进行逐个比较，如果不相同的字符大于1个，则返回false，否则返回true。

5 代码

class Solution {
public:
    bool oneEditAway(string first, string second) {
        int diff=first.size()-second.size();
        int abdiff=abs(diff);
        if(abdiff>1)//false情况
            return false;
        else if(first==second)//零次编辑
            return true;
        else if(abdiff==1)//插入或删除
        {
            int cnt=0;
            for(int i=0,j=0;i<first.size()&&j<second.size();i++,j++)
            {
                if(first[i]!=second[j])
                {
                    cnt++;
                    if(diff<0)
                        i--;
                    else
                        j--;
                }
                if(cnt>1)
                    return false;
            }
            return true;
        }
        else//替换
        {
            int flag=0;
            for(int i=0,j=0;i<first.size()&&j<second.size();i++,j++)
            {
                if(flag&&first[i]!=second[j])
                    return false;
                if(first[i]!=second[j])
                    flag=1;
            }
            return true;
        }
    }
};