Easy to understand C++ solution


  • 0
    P

    If two strings S and T have one edit distance, there are three possibilities:

    1. S.length() == T.length(), there is only one i (0 <= i < S.length()) such that S[i] != T[i]
    2. S.length() == T.length() + 1, there is one i (0 <= i < T.length()) such that S[0...i-1] == T[0...i-1] and S[i+1...S.length()-1] == T[i...T.length()-1]
    3. Same as 2, but T is one character longer than S

    My solution is based on the above idea.

    bool isOneEditDistance(string s, string t) {
        int m = s.length(), n = t.length(), i, j;
        if (m-n >= 2 || m-n <= -2) {
            return false;
        }
    
        bool edit = false;
        for (i=j=0; i<m && j<n; ) {
            if (s[i] == t[j]) {
                i++, j++;
            } else {
                if (edit) return false;
                edit = true;
                if (m == n) { i++, j++; }  // case 1
                else if (m > n) { i++; }   // case 2
                else { j++; }              // case 3
            }
        }
    
        // If this is true, only possible situation is their length differ by 1,
        // and that the last character of the longer is missing from the shorter.
        if (i<m || j<n) edit = true;
        return edit;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.