leetcode算法题--一次编辑

左手的ㄟ右手 2022-12-14 13:51 184阅读 0赞

### 题目描述 ###

*  示范
 *   *  思路分析
     *   *  代码实现

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

# 示范 #

输入: 
    first = "pale"
    second = "ple"
    输出: True
    输入: 
    first = "pales"
    second = "pal"
    输出: False

## 思路分析 ##

遇到这种题目，我们需要分几类情况进行讨论，（1）如果first的字符等于second字符，意味没有进行修改，返回True，接着我们需要根据两字符的长度关系进行判断，（2）如果某一个字符的长度与另一个字符的长度之差的绝对值大于1，则说明这个修改不是一次编辑，返回True。（3）如果两个字符长度相同，则我们需要逐个比较，从第一个开始比较，通过count计数器，如果字符不相同的个数大于1，则说明这个修改不是一次编辑。  
（4）当长度不相同的时候，需要交换两个字符，让比较长的字符作为参考，将每一个first中的元素替代为空格如果和second的的替换相等，返回True

### 代码实现 ###

class Solution:
        def oneEditAway(self, first: str, second: str) -> bool:
            i,j,count=0,0,0
            if first==second:
                return True
            elif abs(len(first)-len(second))>=2:
                return False
            elif len(first)==len(second):
                while i<len(first):
                    if first[i]!=second[j]:
                        count+=1
                        if count>1:
                            return False
                    i+=1
                    j+=1
            elif len(first)<len(second):
                first,second=second,first
                for char in first:
                    if first.replace(char,'')==second.replace(char,''):
                        return True
                    else:
                        return False