4ms 11-lines C++ Solution with Explanations


  • 27

    To solve this problem, you first need to know what is edit distance. You may refer to this wikipedia article for more information.

    For this problem, it implicitly assumes to use the classic Levenshtein distance, which involves insertion, deletion and substitution operations and all of them are of the same cost. Thus, if S is one edit distance apart from T, T is automatically one edit distance apart from S.

    Now let's think about all the possible cases for two strings to be one edit distance apart. Well, that means, we can transform S to T by using exactly one edit operation. There are three possible cases:

    1. We insert a character into S to get T.
    2. We delete a character from S to get T.
    3. We substitute a character of S to get T.

    For cases 1 and 2, S and T will be one apart in their lengths. For cases 3, they are of the same length.

    It is relatively easy to handle case 3. We simply traverse both of them and compare the characters at the corresponding positions. If we find exactly one mismatch during the traverse, they are one edit distance apart.

    Now let's move on to cases 1 and 2. In fact, they can be merged into one case, that is, to delete a character from the longer string to get the shorter one, or equivalently, to insert a character into the shorter string to get the longer one.

    We will handle cases 1 and 2 using the shorter string as the reference. We traverse the two strings, once we find a mismatch. We know this position is where the deletion in the longer string happens. For example, suppose S = "kitten" and T = "kiten", we meet the first mismatch in the 4-th position (1-based), which corresponds to the deleted character below, shown in between *. We then continue to compare the remaining sub-string of T (en) with the remaining sub-string of S (en) and find them to be the same. So they are one edit distance apart.

    S: k i t t e n

    T: k i t *t* e n

    In fact, cases 1, 2 and 3 can be further handled using the same piece of code. For strings of the same length, once we find a mismatch, we just substitute one to be another and check whether they are now the same. For strings of one apart in lengths, we insert the deleted character of the longer string into the shorter one and compare whether they are the same.

    The code is as follows. If you find the first half of the return statement (!mismatch && (n - m == 1)) hard to understand, run the code on cases that the mismatch only occurs at the last character of the longer string, like S = "ab" and T = "abc".

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

  • 0
    C

    Nice one, easy to understand.


  • 7
    T

    Nice explanation. The variable "mismatch" is unnecessary. Here is a cleaner version which is easier to understand.

    class Solution {
    public:
        bool isOneEditDistance(string s, string t) {
            int m = s.size(), n = t.size();
            if (m > n) return isOneEditDistance(t, s);
            if (n - m > 1 || s == t) return false;
            for (int i = 0; i < m; i++)
                if (s[i] != t[i]) {
                    if (m == n) s[i] = t[i];
                    else s.insert(i, 1, t[i]);
                    break;
                }
            return s == t || s + t[n - 1] == t;
        }
    };

  • 0
    J

    Thanks for this code! This is very easy to understand. Brilliant idea!!!


  • 3
    Z

    I think maybe you don't have to actually manipulate the string, we could count the number of differences instead, if differences is more than one, return false.

    bool isOneEditDistance(string s, string t) {
        const int m = s.length(), n = t.length();
        if(m < n) return isOneEditDistance(t, s);
        if(s.compare(t) == 0 || m - n > 1) 
            return false;
        int i = 0, j = 0, cnt = 0;
        while(i < m && j < n){
            if(s[i] != t[j]){
                if(++cnt > 1)       //more than one difference 
                    return false;
                if(m != n){         //move to the next position
                    i++;
                    continue;
                }
            }
            i++, j++;
        }
        return true;
    }

  • 0
    R

    @jianchao-li-fighter

    I have question about the last line
    return (!mismatch && n - m == 1) || (mismatch && s == t);

    why do you return (!mismatch && n - m == 1)?


  • 0
    L

    @zengrui184 great


  • 0
    L
    This post is deleted!

  • 0
    J

    @randy_wales Because the for loop goes through the shorter string, there is possibility that s and t only un-match at the end of the longer one.


Log in to reply
 

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