[LeetCode]161. 相隔为 1 的编辑距离

题目

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

注意：
满足编辑距离等于 1 有三种可能的情形：
往 s 中插入一个字符得到 t
从 s 中删除一个字符得到 t
在 s 中替换一个字符得到 t

样例

示例 1：

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

示例 2:

输入: s = "cab", t = "ad"
输出: false
解释: 无法通过 1 步操作使 s 变为 t。

示例 3:

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

方法1：比较字符串

public static void main(String[] args) {
    
    _1st handler = new _1st();
    String s = "ab", t = "acb";
    Assert.assertTrue(handler.isOneEditDistance(s, t));
    s = "cab";
    t = "ad";
    Assert.assertFalse(handler.isOneEditDistance(s, t));
    s = "1203";
    t = "1213";
    Assert.assertTrue(handler.isOneEditDistance(s, t));


}


public boolean isOneEditDistance(String s, String t) {
    
    int sn = s.length(), tn = t.length();
    //维持s的长度小于t
    if (sn > tn) {
    
        return isOneEditDistance(t, s);
    }
    if (tn - sn > 1) return false;//相隔大于1时，返回false
    for (int i = 0; i < sn; i++) {
    
        if (s.charAt(i) != t.charAt(i)) {
    
            //s与t的长度相同，比较后面的
            if (sn == tn) {
    
                return s.substring(i + 1).equals(t.substring(i + 1));
            } else {
    //s与t的长度不同 s的字符短
                return s.substring(i).equals(t.substring(i + 1));
            }
        }
    }
    return sn + 1 == tn;
}