leetcode161. 相隔为 1 的编辑距离

清疚 2023-07-02 11:24 6阅读 0赞

给定两个字符串 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。

思路：很简单，你可以三个情形都对应的遍历一遍判断即可。

但是稍微有一点优化，其实如果s能删除一个字符变成t，那么t一定也可以插入一个字符得到s。

所以删除插入没必要都写，我们把短的字符串放在左边（s)，就不用写删除了。

class Solution {
      public boolean isOneEditDistance(String s, String t) {
        int ns = s.length();
        int nt = t.length();
        //交换
        if (ns > nt)
          return isOneEditDistance(t, s);
        //长度差超过1
        if (nt - ns > 1)return false;
        //找到不同的字符
        for (int i = 0; i < ns; i++)
          if (s.charAt(i) != t.charAt(i))
            //如长度不同，那么两字符串后面应该相同
            if (ns == nt)
              return s.substring(i + 1).equals(t.substring(i + 1));
            //如长度不同，那么必须在s[i]插入t[i]，所以要保证s.substring(i).equals(t.substring(i + 1))
            else
              return s.substring(i).equals(t.substring(i + 1));
        return (ns + 1 == nt);
      }
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9mYW50aWFuenVvLmJsb2cuY3Nkbi5uZXQ_size_16_color_FFFFFF_t_70][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9mYW50aWFuenVvLmJsb2cuY3Nkbi5uZXQ_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200129162214727.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9mYW50aWFuenVvLmJsb2cuY3Nkbi5uZXQ=,size_16,color_FFFFFF,t_70