161. 相隔为 1 的编辑距离

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

注意：满足编辑距离等于 1 有三种可能的情形

1. 往 s 中插入一个字符得到 t
2. 从 s 中删除一个字符得到 t
3. 在 s 中替换一个字符得到 t

示例 1：

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

示例 2:

输入: s = "1203", t = "1213"
输出: true
解释: 可以将字符串 s 中的 '0' 替换为 '1' 来得到 t。

两个字符串必有公共部分且公共部分只有一个元素，才能用一次操作编辑成一样。

只需用双指针把公共部分筛掉，考察非公共部分。

• 两个字符串不等时，非公共部分差一个元素，用一次插入或删除变成一样。

• 两个字符串相等时，非公共部分元素不同，用一次修改操做将两个字符串变成一样。

s="ab" 与 t="acb"
排除公共部分，就是考察 '' 与 'c'，显然只要在 s 中插入 'c' 即可
s="1203" 与 t="1213"
排除公共部分，就是考察 '0' 与 '1'，显然只要把 s 中的 `0` 变成 `1`即可

时间复杂度： O ( N ) O(N) O(N)，数组所有元素最多遍历一次

空间复杂度： O ( 1 ) O(1) O(1)

class Solution {
    public boolean isOneEditDistance(String s, String t) {
        int n = s.length(), m = t.length();
        if (Math.abs(n - m) > 1) return false;
        if (n > m) return isOneEditDistance(t, s);

        int i = 0, j = n - 1, k = m -1;
        while (i <= j) {
            if (s.charAt(i) != t.charAt(i) && s.charAt(j) != t.charAt(k))
                break;
            if (s.charAt(i) == t.charAt(i)) i++;
            if (s.charAt(j) == t.charAt(k)) { j--; k--; }
        }

        return n == m ? i == j : i > j;
    }
}

Java 代码臃肿，看起来费劲可以看下面 C++ 代码。

class Solution {
public:
    bool isOneEditDistance(string s, string t) {
        int n = s.size(), m = t.size();
        if (abs(n - m) > 1) return false;
        if (n > m) return isOneEditDistance(t, s);

        int i = 0, j = n - 1, k = m - 1;
        while (i <= j) {
            if (s[i] != t[i] and s[j] != t[k]) break;
            if (s[i] == t[i]) i++;
            if (s[j] == t[k]) j--, k--;
        }
        
        return n == m ? i == j : i > j;
    }
};