【程序员面试金典】01.05. 一次编辑

一次编辑

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

示例 1：

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

示例 2：

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

示例 3：

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

示例 4：

输入:
first = “pale”
second = “bake”
输出: False

题目解法

解法 1

该题目可借助蛮力法，通过移除每一个字符(并比较)，替换每一个字符(并比较)，插入每一个字符(并比较)等方法，得到所有可能的字符串，然后检查只需一次编辑的字符串。（该算法运行时间过于缓慢，因此不用费尽心思来实现）

对于此类问题，思考一下每种操作的“意义”大有裨益。两个字符串之间需要一次插入、替换或删除操作意味着什么？

• 替换。 设想一下诸如bale和pale这样的两个字符串，它们之间相差一次替换操作。这确实意味着你可以通过替换bale中的一个字母来获得pale，但是更精确的说法是，这两个字符仅在一个位置上有所不同。
• 插入。 字符串apple和aple之间相差一次插入操作。这意味着，如果你对比两个字符串，会发现除了在字符串的某一位置需要整体移动一次以外，它们是完全相同的。
• 删除。 字符串apple和aple之间同样也可以表示为相差一次删除操作，因为删除操作只是“插入”操作的相反操作而已。

实现算法时，会把插入和删除合并为一个步骤，而让替换操作成为一个单独的步骤。

算法实现（JAVA）

public class Solution {
    public boolean oneEditAway(String first, String second) {
        if (first.length() == second.length()) {
            // 替换
            return oneEditReplace(first, second);
        } else if (first.length() + 1 == second.length()) {
            // 删除
            return oneEditInsert(first, second);
        } else if (first.length() - 1 == second.length()){
            // 插入
            return oneEditInsert(second, first);
        }
        return false;
    }

    private boolean oneEditReplace(String first, String second) {
        boolean foundDifference = false;
        for (int i = 0; i < first.length(); i++) {
            if (first.charAt(i) != second.charAt(i)) {
                if (foundDifference) {
                    return false;
                }
                foundDifference = true;
            }
        }
        return true;
    }

    private boolean oneEditInsert(String first, String second) {
        int index1 = 0;
        int index2 = 0;
        while (index2 < second.length() && index1 < first.length()) {
            if (first.charAt(index1) != second.charAt(index2)) {
                if (index1 != index2) {
                    return false;
                }
            } else {
                index1++;
            }
            index2++;
        }
        return true;
    }

    public static void main(String[] args) {
        Solution1 solution = new Solution1();
        String first = "islander";
        String second = "slander";
        // true
        System.out.println(solution.oneEditAway(first, second));
    }
}
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
50
51
52

解法 2

解法1中方法oneEditReplace和oneEditInsert代码相差无几。因此，可以将二者合并为一个方法。

为达到该目的，请注意这两种方法的解题思路大体相似，即对比每个字符并确保两个字符串只相差一个字符。两种方法的不同之处在于如何处理不同的字符。oneEditReplace方法除了标出不同的字符之外不做任何操作，oneEditInsert方法则将较长字符串的指针向前移动。可以用同一种方法处理这两种情况。

算法实现（JAVA）

public class Solution {
    public boolean oneEditAway(String first, String second) {
        // 检查长度
        if (Math.abs(first.length() - second.length()) > 1) {
            return false;
        }

        // 获取较长和较短的字符串
        String s1 = first.length() < second.length() ? first : second;
        String s2 = first.length() < second.length() ? second : first;

        int index1 = 0;
        int index2 = 0;
        boolean foundDifference = false;
        while (index1 < s1.length() && index2 < s2.length()) {
            if (s1.charAt(index1) != s2.charAt(index2)) {
                // 确保此处为发现的第一处不同
                if (foundDifference) {
                    return false;
                }
                foundDifference = true;
                if (s1.length() == s2.length()) {
                    index1++;
                }
            } else {
                index1++; // 如果相匹配，就移动较短字符串的指针
            }
            index2++; // 总是移动较长字符串的指针
        }
        return true;
    }
}
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

[1] 盖尔.拉克曼.麦克道尔.程序员面试金典（第6版）[M].北京：人民邮电出版社，2019.9：162-164
[2] leetcode.面试题 01.05. 一次编辑