leetcode原题一次编辑（判定字符串是否只需要一次(或者零次)编辑）-Toy模板网

这篇具有很好参考价值的文章主要介绍了leetcode原题一次编辑（判定字符串是否只需要一次(或者零次)编辑）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目：

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

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

解题思路：

本题可以分为以下几种情况来处理：

1.两个字符串长度相差=1，那么只需要判断哪个字符串更长，再判断将短字符串插入一个字符串后，是否符合条件

2.两个字符串长度相等，那么只能进行替换，不能插入

3.两个字符串长度相差>1,那么一次编辑是无法使两个字符串相等的，直接返回false即可

源代码如下：文章来源地址https://www.toymoban.com/news/detail-636783.html

class Solution {
public:
    bool oneEditAway(string first, string second) {
        int len1=first.size();
        int len2=second.size();
        //第一个字符串比第二个字符串长度多1个字符
        if(len1-len2==1)
        {
            //给第二个字符串插入一个字符，判断是否跟第一个字符串相等
            return insert(first,second);
        }
        //第二个字符串比第一个字符串长度多1个字符
        else if(len2-len1==1)
        {
            //给第一个字符串插入一个字符，判断是否跟第二个字符串相等
            return insert(second,first);
        }
        //两个字符串长度相等，那么只能通过替换实现，不能进行插入
        else if(len1==len2)
        {
            return replace(first,second);
        }
        //剩下的情况：两个字符串长度相差大于1，不能只通过一次编辑实现
        else
        {
            return false;
        }
    }
    //插入函数
    bool insert(string Long, string Short)
    {
        int i,j=0;
        while(i<Long.size()&&j<Short.size())
        {
            //如果两个字符相等
            if(Long[i]==Short[j])
            {
                //短字符下标继续走
                j++;
            }
            i++;
            //当下标i和j差值大于1时，说明 不止需要插入一个字符
            if(i-j>1) return false;
        }
        return true;
    }
    //替换函数
    bool replace(string first, string second)
    {
        int i=0;
        int flag=0;//标记是否已经覆盖过
        while(i<first.size())
        {
            if(first[i]!=second[i])
            {
                //如果两个字符不相等的同时，flag还大于0，说明前面已经替换过一次了，直接返回false
                if(flag>0)
                {
                    return false;
                }
                //若能替换，则flag++
                flag++;
            }
            i++;
        }
        return true;
    }
};

到了这里，关于leetcode原题一次编辑（判定字符串是否只需要一次(或者零次)编辑）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！