[数据结构与算法]面试题01.05一次编辑

一次编辑

题目描述：

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

题目链接：面试题 01.05. 一次编辑

示例1：

输入: 
first = "pale"
second = "ple"
输出: True

示例2：

输入: 
first = "pales"
second = "pal"
输出: False

解题思路：

首先我们得明白一件事情，两个字符串能够通过对方插入一个字符、删除一个字符串或者替换一个字符得来。那么证明他们长度之差一定是小于等于1的，因此我们可以先特判一下只要他们两个的长度差大于1直接返回false。

这里说一个小细节：不管是first字符串长还是second字符串长，我们都让长的字符串是first！！！

然后再来说思路：

经过上面的处理接下来就只要考虑两种情况：

• first字符串与second字符串相等，遍历两个字符串并且用一个变量用来记录他们两个字符串之间有多少个字符不同，只要这个变量大小超过1就直接返回false，因为他们不可能通过替换一个字符得到。如果这个变量的大小是小于等于1的则返回true

• first字符串与second字符串长度的差值为1，遍历两个字符串并且用一个变量来记录他们两个字符串之间有多少个字符不同，这个变量大小如果是小于等于1的，那么first就可以通过second插入一个字符得到或者说second就可以通过first删除一个字符得到。但是这个变量大小只要是大于1的，那么他们俩就一定不能通过一次编辑得到，反之则可以通过一次编辑得到

需要注意的是：当是第二种情况的时候，遍历的时候，如果此时first的字符与second的字符是不相等的，我们要让first后移，而不是second后移，因为有可能first就是比second多了这个字符，并且我们通过变量来记录它俩不同的字符个数也是想知道second字符串的所有字符是否都在first出现过。

代码

class Solution {
public:
    bool oneEditAway(string first, string second) {
        //记录first字符串的长度
        int n1 = first.size();
        //记录second字符串的长度
        int n2 = second.size();

        //不管是first是长的字符串还是second是长的字符串 我们都让first是长的字符串
        if(n1<n2)
        {
            swap(first,second);
        }
        
        //如果他们的字符串长度差的绝对值大于1，直接返回false
        if(abs(n1-n2)>1)
        {
            return false;
        }

        //如果seconde字符串是first字符串插入，删除或者替换一个字符变来的
        //那么就只有三种情况
        //1.first的长度小于second，first是second的子串
        //2.first的长度等于second，但是first和second有一个字符不相同
        //3.first的长度大于second，secon是first的子串
        
        //如果first长度等于second的长度
        if(n1==n2)
        {
            //用来记录两个字符串中有多少个不同的字符
            int sum = 0;
            for(int i = 0;i<n1;i++)
            {
                if(first[i]!=second[i])
                {
                    sum++;
                }
            }
            //如果sum是小于等于1的就是一次(或者零次编辑)而来的
            return sum<=1;
        }
        //first与second的长度不相等，差值为1
        else
        {
        //双指针做法
        //i指向first字符串,j指向second字符串
        int i = 0;
        int j = 0;
        //用来记录两个字符串中有多少个不同的字符
        int count = 0;
        while(i<n1&&j<n2)
        {
            if(first[i]==second[j])
            {
                i++;
                j++;
            }
            else
            {
                count++;
                //只要不同的字符超过一个就返回false
                if(count>1)
                {
                    return false;
                }
                i+=count;
            }
        }
        }
        return true;

    }
};