快捷搜索: 长连接 前端 源码 pan

(C++/Python)LeetCode 面试题01.05 一次编辑

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

思路: 因为只能进行一次编辑,所以当两个字符串的长度差值大于1的时候,肯定进行一次编辑是不行的,只能f返回false; 当差值为1时,可以进行插入或者删除 当差值为0时,只能进行替换

代码如下: C++:

class Solution {
          
   
public:
    bool oneEditAway(string first, string second) {
          
   
        int len=first.size()-second.size();
        if(len>1||len<-1)  {
          
   
            return false;
        } 
        int flag=0;
        for(int i=0,j=0;i<first.size()&&j<second.size();i++,j++){
          
   
            if(first[i]!=second[j]){
          
   
                if(len==1){
          
    //要不要删除
                    j--;//注意这里,注释写在下面
                    flag++;
                }
                else if(len==-1){
          
    //要不要插入
                    i--;//如下注
                    flag++;
                }
                else if(len==0){
          
   //要不要替换
                    flag++;
                }
            }
            if(flag>1)
            return false;
        }          
        return true;
    }
};

当len =1的时候,说明first长度长,此时需要删除一个,i++就行啦,,但是此时 j 不能变,(还需要进行比较),因为是在一个for 循环里面,之后 i 和 j 都要再++,所以此时只能把 j --,这样后面再++,就能保证 j 不变 下面的那个同理

Python:

class Solution:
    def oneEditAway(self, first: str, second: str) -> bool:
        m=len(first)
        n=len(second)
        if abs(m-n)>1:
            return False
        for i in range(min(m,n)):
            if first[i]==second[i]:
                i+=1
            else:
                return first[i+1:]==second[i+1:] or first[i+1:]==second[i:] or first[i:]==second[i+1:]
        return True
经验分享 程序员 微信小程序 职场和发展