161. One Edit Distance

今儿做微软的OA遇上了这个原题,赶紧来总结一下.
思路: 找编辑距离为1,也就是给的两个字符串中,只有一个字符不同,或者字符缺失. 分以下几种情况讨论:
1. 给定的两个字符串长度相同, 则先找到字符串不同的位置i,然后验证i+1后的子串是否相同即可。
2. 给定的两个字符串长度相差为1, 则先找到第一个对应位置不一样的那个字符,如果较长字符串在那个字符之后的部分和较短字符串那个字符及之后的部分是一样的,则符合要求.
3. 给定的两个字符串长度大于1, 则肯定不符合要求.
复杂度: Time O(n), Space O(1)

public class Solution {
    public boolean isOneEditDistance(String s, String t) {
        int sLen = s.length();
        int tLen = t.length();
        if (sLen == 0 && tLen == 0) return false;
        if (sLen == tLen) return isOneEdit(s, t);
        if (sLen - tLen == 1) return isOneDeleted(s, t);
        if (tLen - sLen == 1) return isOneDeleted(t, s);
        return false;
    }

    public boolean isOneEdit(String s, String t) {
        boolean isModified = false;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) != t.charAt(i)) {
                if (isModified) return false;
                else isModified = true;
            }
        }
        return isModified;
    }

    public boolean isOneDeleted(String longStr, String shortStr) {
        for (int i = 0; i < shortStr.length(); i++) {
            if (longStr.charAt(i) != shortStr.charAt(i)) {
                return longStr.substring(i+1).equals(shortStr.substring(i));
            }
        }
        return true;
    }
}
Advertisements