首先如果字符相差超过一个, 必然为false
one edit 分为三种情况
s = abcde
t1 = abcdex
t2 = abcxe
t3 = abcxde
这三种情况都为true
time O(n) space O(1)
public class Solution {
public boolean isOneEditDistance(String s, String t) {
int m = s.length();
int n = t.length();
if (m > n) {
return isOneEditDistance(t, s);
}
if (n - m > 1) {
return false;
}
int i = 0;
while (i < m && s.charAt(i) == t.charAt(i)) {
i++;
}
if (i == m) {//case t: abcdex
return n - m == 1;
}
if (m == n) {//case t: abcxd
i++;
while (i < m && s.charAt(i) == t.charAt(i)) {
i++;
}
}
if (n - m == 1) {// case t: abcxde
while (i < m && s.charAt(i) == t.charAt(i + 1)) {
i++;
}
}
return i == m;
}
}
没有评论:
发表评论