给定两个字符串 s 和 t,判断他们的编辑距离是否为 1。java
注意:优化
知足编辑距离等于 1 有三种可能的情形:code
往 s 中插入一个字符获得 t
从 s 中删除一个字符获得 t
在 s 中替换一个字符获得 t
示例 1:blog
输入: s = "ab", t = "acb"
输出: true
解释: 能够将 'c' 插入字符串 s 来获得 t。
示例 2:字符串
输入: s = "cab", t = "ad"
输出: false
解释: 没法经过 1 步操做使 s 变为 t。
示例 3:string
输入: s = "1203", t = "1213"
输出: true
解释: 能够将字符串 s 中的 '0' 替换为 '1' 来获得 t。it
思路:很简单,你能够三个情形都对应的遍历一遍判断便可。io
可是稍微有一点优化,其实若是s能删除一个字符变成t,那么t必定也能够插入一个字符获得s。class
因此删除插入不必都写,咱们把短的字符串放在左边(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); } }