淘宝联盟微信里做网站,企业营销策划推广,网络营销模式包括哪些,游戏软件开发定制161.相隔为1的编辑距离 方法#xff1a;一次遍历
首先#xff0c;我们要确认字符串的长度不会相差太远。如果长度差了2个或更多字符#xff0c;那么 s 和 t 就不可能是一次编辑之差的字符串。
接下来#xff0c;我们假设 s 的长度总是短于或等于 t 的长度。如果不是这样一次遍历
首先我们要确认字符串的长度不会相差太远。如果长度差了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;ins;i){if(s.charAt(i) ! t.charAt(i)){//如果字符串具有相同的长度if(nsnt){return s.substring(i1).equals(t.substring(i1));}elsereturn s.substring(i).equals(t.substring(i 1));}}return (ns 1 nt);}
}
