161. One Edit Distance - cocoder39/coco39_LC GitHub Wiki

161. One Edit Distance

exactly one distance not no more than one distance.

• In case if (s.length() == t.length()), only replacing is allowed
• In case if (abs((s.length() - t.length()) == 1), only deleting/inserting is allowed

bug report: if (abs((s.length() - t.length()) > 1) will generate a bug because the type of s.length() is unsigned int, which makes the negative value problematic.

O(n)

//either insert, delete or replace
    bool isOneEditDistance(string s, string t) {
        if (abs((int)(s.length() - t.length()) > 1)   
            return false;

        if (s.length() == t.length()) { //able to replace
            for (int i = 0; i < s.length(); i++) {
                if (s[i] != t[i])   
                    return s.substr(i + 1) == t.substr(i + 1);
            }
            return false;
        }
        else { //insert/delete
            string& lon = s.length() > t.length() ? s : t;
            string& sho = s.length() > t.length() ? t : s;
            for (int i = 0; i < sho.length(); i++) {
                if (sho[i] != lon[i]) 
                    return lon.substr(i + 1) == sho.substr(i);
            }
            return true;
        }
    }

second round

bool isOneEditDistance(string s, string t) {
        int m = s.length(), n = t.length();
        if (abs(m - n) > 1 || s == t)   return false;
        
        int i = 0;
        for (; i < m && i < n; i++) {
            if (s[i] != t[i])   break;
        }
        
        if (m == n) { //replace
            return s.substr(i + 1) == t.substr(i + 1);
        } else if (m > n) { //insert or delete
            return s.substr(i + 1) == t.substr(i);
        } else {
            return s.substr(i) == t.substr(i + 1);
        }
    }

3rd

class Solution {
public:
    bool isOneEditDistance(string s, string t) {
        int m = s.length(), n = t.length();
        if (abs(m - n) > 1) return false;
        
        int i = 0;
        for (; i < m && i < n; i++) {
            if (s[i] != t[i])   break;
        }
        
        if (m == n) {
            if (i == m) {
                return false;
            } else {
                return isSame(s, i + 1, t, i + 1, m - i);
            }
        } else if (m > n) {
            return isSame(s, i + 1, t, i, n - i);
        } else {
            return isSame(s, i, t, i + 1, n - i);
        }
    }
private:
    bool isSame(string& s, int ss, string& t, int ts, int len) {
        for (int i = 0; i < len; i++) {
            if (s[ss + i] != t[ts + i]) return false;
        }
        return true;
    }
};