【LeetCode刷题】-- 161.相隔为1的编辑距离

161.相隔为1的编辑距离

方法：一次遍历

首先，我们要确认字符串的长度不会相差太远。如果长度差了2个或更多字符，那么 s 和 t 就不可能是一次编辑之差的字符串。

接下来，我们假设 s 的长度总是短于或等于 t 的长度。如果不是这样，人们总是可以调用 isOneEditDistance(t, s) 来逆转字符串的顺序。
现在是时候沿着字符串前进，寻找第一个不同的字符了。
如果前 len(s) 字符没有差异，只有两种可能的情况:

• 字符串是相等的。
• 字符串是一次编辑之差的距离。

那么如果存在一个不同的字符，使得 s[i] != t[i] 呢？

• 如果字符串长度相同，为了保持一次编辑之差的距离，_所有_后面的字符应该是相同的。为了验证这一点，人们需要比较 s 和 t 的子字符串，它们都从 i + 1 的字符开始。
• 如果 t 比 s 长一个字符，那么额外的字符 t[i] 应该是这两个字符串之间的唯一区别。为了验证这一点，人们需要比较一个从 s 的 i 字符开始的子字符串和一个从 t 的 i + 1 字符开始的子字符串。

class Solution {
    public boolean isOneEditDistance(String s, String t) {
        int ns = s.length();
        int nt = t.length();

        //确保s比t短
        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));
                }else
                    return s.substring(i).equals(t.substring(i + 1));

            }
        }
        return (ns + 1 == nt);
    }
}