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));}elsereturn s.substring(i).equals(t.substring(i + 1));}}return (ns + 1 == nt);}
}