2015年9月10日星期四

One Edit Distance

Given two strings S and T, determine if they are both one edit distance apart.

public class Solution {
    public boolean isOneEditDistance(String s, String t) {
        if (s == null || t == null) {
            return false;
        }
        if (s.length() > t.length()) {
            return isOneEditDistance(t, s);
        }
        if (s.length() == t.length()) {
            boolean diff = false;
            for (int i = 0; i < s.length(); i++) {
                int c1 = s.charAt(i);
                int c2 = t.charAt(i);
                if (c1 != c2) {
                    if (diff) return false;
                    diff = true;
                }
            }
            return diff;
        } else if (s.length() + 1 == t.length()) {
            int start = 0;
            while (start < s.length() && s.charAt(start) == t.charAt(start)) {
                start++;
            }
            while (start < s.length() && s.charAt(start) == t.charAt(start + 1)) {
                start++;
            }
            return start == s.length();
        } else {
            return false;
        }
    }
}
=========

public class Solution {
    public boolean isOneEditDistance(String s, String t) {
        if (s == null || t == null) {
            return false;
        }
        if (s.length() == t.length()) {
            return isModify(s, t);
        } else if (s.length() - t.length() == 1) {
            return isDelete(s, t);
        } else if (s.length() - t.length() == -1) {
            return isDelete(t, s);
        } else {
            return false;
        }
    }
   
    private boolean isDelete(String s, String t) {
        for (int i = 0; i < t.length(); i++) {
            if (s.charAt(i) != t.charAt(i)) {
                return s.substring(i + 1).equals(t.substring(i));
            }
        }
        return true;
    }
   
    private boolean isModify(String s, String t) {
        boolean modify = false;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) != t.charAt(i)) {
                if (modify) return false;
                modify = true;
            }
        }
        return modify;
    }
}

没有评论:

发表评论