首先如果字符相差超过一个, 必然为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; } }
没有评论:
发表评论