01.05一次编辑

面试题 01.05. 一次编辑

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

示例 1:

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

示例 2:

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

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

题解：

分三种情况:

两个字符串长度相等，则只有1次或者0次替换。遍历记录字符不同的次数，diffcnt <= 1时 return true. 否则 return false
两个字符串长度相差超过1，一次编辑不能处理，直接return false
两个字符串长度相差等于1，则为一次删除/添加

代码如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49


public boolean oneEditAway(String first, String second) {

        int len1 = first.length();
        int len2 = second.length();

        // 长度相差超过1， 一次编辑不能处理
        if (Math.abs(len1 - len2) > 1) return false;

        if (len1 == len2){
            // 长度相同
            // 一次编辑 -> 替换
            int diffcnt = 0;
            for (int i = 0; i < len1; i++) {
                if (first.charAt(i) != second.charAt(i))  diffcnt ++;
              
              	if(diffcnt > 1) return false;
            }
            return diffcnt <= 1;
        }else {

            // 保证 first串 比 second串 长
            if (len2 > len1) return oneEditAway(second,first);

            // 长度相差 1
            // 一次编辑 -> 添加/删除
            // 双指针，i用来遍历 first
            // j 用来遍历 second
            int i = 0, j = 0;
            while (i < len1 && j < len2){
                char c1 = first.charAt(i);
                char c2 = second.charAt(j);

                // 相等 两个指针都向右移动一位
                if (c1 == c2){
                    i ++;
                    j ++;
                    continue;
                }

                // 已经有一次不想等，指针后移，再次不想等， 直接return false. 
                if (i != j) return false;

                // 第一次不相等
                i ++;
            }
        }

        return true;
    }

时间复杂度: O(m + n)

空间复杂度: O(1)

Contents

面试题 01.05. 一次编辑

题解：