Leetcode 面试题 01.05. 一次编辑

- 日理万妓 2022-09-03 00:08 119阅读 0赞

#### 题目重述 ####

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

##### 示例 1: #####

输入:  
first = “pale”  
second = “ple”  
输出: True

##### 示例 2: #####

输入:  
first = “pales”  
second = “pal”  
输出: False

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/one-away-lcci  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

#### 思路 ####

也可以直接用编辑距离的动态规划算法，最后判断编辑次数是否超过1即可，但是时间复杂度会高

#### Java实现 ####

class Solution {
        
        // 测试用例:"horse"
        //			"ros"
        // first = "pale"
        //second = "ple"
        public boolean oneEditAway(String first, String second) {
        
            // 两个字符差距如果大于1，不可能1次操作完成
            int len = first.length() - second.length();
            if (len > 1 || len < -1) {
        
                return false;
            }
            int count = 0;
            int i = 0, j = 0;
    
            while (i < first.length() && j < second.length()) {
        
                if (first.charAt(i) != second.charAt(j)) {
        
                    //second要不要添加一个字符
                    if (len == 1) {
        
                        j--;
                    }
                    //second要不要删除一个字符
                    else if (len == -1) {
        
                        i--;
                    }
                    count++;
                }
                //最多编辑一次
                if (count > 1) {
        
                    return false;
                }
                i++;
                j++;
            }
            return true;
        }
    }