一次编辑（只需要插入、删除或替换）的字符串

傷城~ 2023-02-18 11:53 20阅读 0赞

> 字符串有三种编辑操作:插入一个字符、删除一个字符或者替换一个字符。 给定两个字符串，编写一个函数判定它们是否只需要一次(或者零次)编辑。  
>   
> 示例 1:  
> 输入:  
> first = “pale”  
> second = “ple”  
> 输出: True  
>   
> 示例 2:  
> 输入:  
> first = “pales”  
> second = “pal”  
> 输出: False

### 分析 ###

没什么好分析的，题目很直接。

### 一、分开思路 ###

既然题目已经说了：**插入一个字符、删除一个字符** 或者 **替换一个字符**，那么直接按照这种思路写额外的三个方法。

1.  插入 和 删除是倒过来的一样方法，也就是长度差 1 且除了差的这一个，其他完全一样。
2.  完全一样，长度差 0 ，这种情况可能 (1) 完全相等，(2) 可能差一个，或者(3) 差超过两个（false）；
3.  长度差超过两个。

这样就可以写出一个冗余度比较高，但是正确的代码：

class Solution {
        
        public boolean oneEditAway(String first, String second) {
        
            char[] a=first.toCharArray();
            char[] b=second.toCharArray();
            if(a.length==0&&b.length==0){
        
                return true;
            }
            if(a.length-b.length>1||a.length-b.length<-1){
        
                return false;
            }
            
            //在保证字符数相差不超过一个的情况下再判断能否通过操作
            boolean ans1= a.length>b.length? oneInsert(a,b): oneInsert(b,a);//删除换成插入，保障第一个长
            boolean ans2=oneSet(a,b);
            return ans1||ans2;
        }
    
        //1.判断插入和删除。删除和插入是一个意思，只不过是两个字符串长度的互换
        public boolean oneInsert(char[] first,char[] second){
        
            if(first.length==second.length){
        
                return false;//规定长度不等
            }
            int a=first.length;
            int b=second.length;
            int pre=0;
            while(pre<a){
        
                if(pre==b||first[pre]!=second[pre]){
        
                    break;
                }
                pre++;
            }
            int after=a-1;
            while(after>=0){
        
                if(after==0||first[after]!=second[after-1]){
        
                    break;
                }
                after--;
            }
            //通过从前和从后，找到出现不一样的位置，
            //如果是同一个位置，说明除了这里之外其他完全相同
            if(pre==after){
        
                return true;
            }else{
        
                return false;
            }
        }
    
        //2.判断修改。改变一个，也就是顺序执行统计不一样的字符数
        public boolean oneSet(char[] first,char[] second){
        
            if(first.length!=second.length){
        
                return false;//相反规定长度相等
            }
            int count=0;
            for(int i=0;i<first.length;i++){
        
                if(first[i]!=second[i]){
        
                    count++;
                }
            }
            if(count>1){
        
                return false;
            }else{
        
                return true;//<1 包括了完全相等，和差一个，也就是可修改
            }
        }
    }

### 二、最多编辑一次 ###

首先，上面的代码是有重复的部分的，比如遍历数组的过程中，我们的两个方法 oneSet 和 oneInsert 都是一个一个判断，在 oneInsert 方法里面，前后遍历，最后对比是否位置相等，这个过程也不简洁。

我们来看一看能不能合并这些操作：

1.  oneInsert 方法在统计是否只需要 insert 一次的过程中，把不一样的位置，跳过了，那么这个位置一定是 两个字符串中较长的那个造成的；
2.  oneSet 方法在统计是否只差一个的过程中，不一样的地方不需要进行操作，只统计了数量，而且找不一样的地方的操作其实也可以用 oneInsert 的方法实现。

显然重复部分可以想办法合并，我们一边统计 count ，一边在看是否需要 insert 的过程中，通过移动较长的字符串的下标，跳过不一样的位置。

这样就只需要一遍循环。总结两个字符串的不同为 **只通过一次操作** 就可以得到另一个：

class Solution {
        
        public boolean oneEditAway(String first, String second) {
        
            int diff=first.length()-second.length();
            if(diff>1||diff<-1){
        
                return false;//相差超过2个字符
            }
            //剩下只可能相差 1 个字符，或者 0 个字符。
            int count=1;//设置为 1，意为通过一次修改
            
            for(int i=0,j=0;i<first.length()&&j<second.length();i++,j++){
        
                if(first.charAt(i)!=second.charAt(j)){
        
                    if(diff==1){
        
                        j--;//diff=1代表 first 字符串比较长，跳过 first.charAt(i)
                    }else if(diff==-1){
        
                        i--;//相反，跳过 second.charAt(i)
                    }
                    count--;//既然有不同，说明有一次修改次数。
                }
                if(count<0){
        
                    return false;//一旦需要修改的次数 >1 立即返回
                }
            }
            return true;
        }
    }