2015年10月6日星期二

One Edit Distance leetcode

Given two strings S and T, determine if they are both one edit distance apart.
首先如果字符相差超过一个, 必然为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;
    }
}

没有评论:

发表评论