题目描述

给定两个字符串 $s$ 和 $t$，判断它们的编辑距离是否为1。

注意：
编辑距离为1有三种情况：

• 在 $s$ 中插入一个字符可以得到 $t$；
• 在 $s$ 中删除一个字符可以得到 $t$；
• 将 $s$ 中的一个字符替换掉可以得到 $t$；

样例1

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

样例2

输入：s = "cab", t = "ad"
输出：false
解释：对s只操作一步无法得到t。

样例3

输入：s = "1203", t = "1213"
输出：true
解释：将s中的0替换成1，可以得到t。

算法

(扫描数组) $O(n)$

分三种情况考虑：

1. 字符串长度之差大于1，则编辑距离一定大于1，返回false；
2. 字符串长度相等，则有且只有一个字符不同时，才返回true；
3. 字符串长度差1，则只需判断短字符串是否是长字符串的子序列即可：用指针 $i$ 指向短字符串开头(不妨设短字符串是 $s$，长字符串是 $t$)，然后扫描长字符串，如果当前字符等于 $s[i]$，则令 $i$ 加1。如果最终 $i$ 能遍历完 $s$，则 $s$ 就是 $t$ 的子序列；

时间复杂度分析：三种情况都只需将两个字符串遍历一次，所以时间复杂度是 $O(n)$。

C++ 代码

class Solution {
public:
    bool isOneEditDistance(string s, string t) {
        if (s.size() > t.size()) swap(s, t);
        if (s.size() + 1 < t.size()) return false;
        if (s.size() == t.size())
        {
            int res = 0;
            for (int i = 0; i < s.size(); i ++ ) res += s[i] != t[i];
            return res == 1;
        }
        int k = 0;
        for (int i = 0; k < s.size() && i < t.size(); i ++ )
            if (t[i] == s[k])
                k ++ ;
        return k == s.size();
    }
};