`

Leetcode - One Edit Distance

 
阅读更多
[分析]
两字符串相同或者长度差异大于等于2都不符合要求,只需要检查那些长度相同或者相差为1的情况。逐个字符检查,发现第一个差异字符,若s和t长度相等将s中字符替换为t中字符,若不等则在s中插入t当前字符,然后跳出检查循环。若检查过程无差异字符(说明长度差1)或者消除发现的第一个差异后两字符串相等说明两字符串编辑距离为1.
这个思路和实现参考https://leetcode.com/discuss/42379/4ms-11-lines-c-solution-with-explanations,自己写的丑代码就不粘贴了

public class Solution {
    public boolean isOneEditDistance(String s, String t) {
        if (s == null || t == null || s.equals(t)) return false;
        int sLen = s.length(), tLen = t.length();
        if (sLen > tLen) return isOneEditDistance(t, s);
        if (sLen + 1 < tLen) return false; // |sLen - tLen| >= 2
        
        boolean misMatch = false;
        for (int i = 0; i < sLen; i++) {
            if (s.charAt(i) != t.charAt(i)) {
                if (sLen == tLen) {// replace the first diff char is s with char of t
                    s = s.substring(0, i) + t.charAt(i) + s.substring(i + 1, sLen);
                } else { // insert curr char of t
                    s = s.substring(0, i) + t.charAt(i) + s.substring(i, sLen);
                }
                misMatch = true;
                break;
            }
        }
        return !misMatch || s.equals(t);
    }
}
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics