拼写纠正系列

开源项目

• nlp-hanzi-similar 汉字相似度
• word-checker 拼写检测
• sensitive-word 敏感词

题目

给定两个字符串 s 和 t，如果它们的编辑距离为 1，则返回 true；否则返回 false。编辑距离为 1 的情况包括：

• 在 s 中插入一个字符得到 t
• 从 s 中删除一个字符得到 t
• 在 s 中替换一个字符得到 t

示例 1：

输入: s = "ab", t = "acb"
输出: true
解释: 可以在 s 中插入字符 'c' 来得到 t。

示例 2:

输入: s = "cab", t = "ad"
输出: false
解释: 无法通过一步操作将 s 转换为 t。

提示:

• 0 <= s.length, t.length <= 10^4
• s 和 t 由小写字母、大写字母和数字组成

方法模板

public boolean isOneEditDistance(String s, String t) {
    // 方法实现
}

基本思路

思路

我们将问题分为三种情况：

1. 如果两个字符串长度差大于 1，则不可能满足条件。
2. 如果两个字符串长度相同，则可能通过替换一个字符来满足条件。
3. 如果长度差为 1，则可能通过插入或删除一个字符来满足条件。

具体实现时，我们可以通过比较两个字符串，找到第一个不同的字符，然后跳过其中一个字符串中的一个字符，继续比较剩余部分。如果剩余部分相等，则返回 true；否则返回 false。

实现

public static boolean isOneEditDistance(String s, String t) {
    int sLen = s.length();
    int tLen = t.length();

    if (Math.abs(sLen - tLen) > 1) {
        return false;
    }

    char[] sChars = s.toCharArray();
    char[] tChars = t.toCharArray();
    if (sLen == tLen) {
        int diffCount = 0;
        for (int i = 0; i < sLen; i++) {
            if (sChars[i] != tChars[i]) {
                diffCount++;
            }
        }

        return diffCount == 1;
    }

    if (s.length() > t.length()) {
        String temp = s;
        s = t;
        t = temp;
    }

    for (int i = 0; i < s.length(); i++) {
        if (s.charAt(i) != t.charAt(i)) {
            return s.substring(i).equals(t.substring(i + 1));
        }
    }
    return s.length() + 1 == t.length();
}

小结

这个问题可以看作是 T72 的简化版，因为它相对简单。

我是老马，期待与你的下次重逢。

开源项目

单词拼写对应的开源项目如下，欢迎 fork + star!

https://github.com/houbb/word-checker

参考资料

• edit-distance-1.html
• Peter Norvig: How to Write a Spelling Corrector.