One Edit Distance

Source

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

题解

如果字符串相差2个以及以上长度,那么肯定不止1,直接false

如果字符串长度相等,那么判断对应位置不同的字符数是不是1即可。

如果字符串长度相差1,那么肯定是要在长的那个串删掉一个,所以两个字符串一起加加,一旦遇到一个不同,那么剩下的子串就要是一样,否则就是不止一个不同,false。

Java

bool isOneDifL(string s, string t){
    for (int i = 0; i < s.size(); i++){
        if (s[i] == t[i])
            continue;
        return s.substr(i) == t.substr(i+1);
    }
    return true; // 说明前面的都相等只有最后一个不匹配
}
bool isSameLen(string s, string t){
    int cnt = 0;
    for (int i = 0; i < s.size(); i++){
        if (s[i] != t[i])
            cnt++;
    }
    return cnt == 1;
}

bool isOneEditDistance(string s, string t){
    if (abs(s.size() - t.size()) > 1) return false;
    if (s.size() == t.size()) return isSameLen(s, t);
    else if (s.size() < t.size()) return isOneDifL(s, t);
    else return isOneDifL(t, s);
}