Return to Revisions

Generally Interview questions check multiple things at once. You for example would have failed in my view, as you wrote a generic solution to a much simpler test.

The title states that the distance should be at most 1, or lets say N. Therefore, you should discard any string that differ in size by more than N, e.g

std::string a(10e5, 'a');
std::string b = a;
b += "bb";

Your algorithm would iterate over the whole string a before it would find the mismatch. Therefore, check for sizes first

bool oneAway(const string& s1, const string& s2)
{
    if ((s1.size() > s2.size() && s1.size() - s2.size() > 1)) {
        (s2.size() > s1.size() && s2.size() - s1.size() > 1)) {
       return false;
    }
...
}

You will see 2 comparisons here because either s1 or s2 may be larger. Make you life simple and simply chose one

bool oneAway(const string& s1, const string& s2)
{
    if ((s2.size() > s1.size()) {
       return oneAway(s2, s1);
    }
    
    // From here s1.size() >= s2.size()
    if ((s1.size() - s2.size() > 1) {
       return false;
    }
...
}

The added benefit would be, that there are only 2 cases left:

1. Equal length -> You can only replace a character so if there is a mismatch only check if there is a second one.

2. Strings differ by 1 -> If there is a mismatch you should realize, that deletion or insertion of characters are equivalent. Consider the following

     s1 = "abc"
     s2 = "ac"
   

   It doesn't matter if you insert b into s1 or delete it from s2. The important part is that the "c" match.

So we can simply check those two cases

bool oneAway(const string& s1, const string& s2)
{
    if ((s2.size() > s1.size()) {
       return oneAway(s2, s1);
    }
    
    // From here s1.size() >= s2.size()
    if ((s1.size() - s2.size() > 1) {
       return false;
    }
        
    auto it_s1 = s1.begin();
    auto it_s2 = s2.begin();
    bool missmatchFound = false;
    for (; it_s2 != s2.end(); ++it_s1, ++it_s2) {
        if (*it_s1 != *it_s2) {
            if (missmatchFound) {
                return false;
            }
            if (it_s2 == s2.end()) {
                return s1.size() == s2.size();
            }
            missmatchFound = true;
            // If both have same size simply search for the second missmatch, so nothing to do
            if (s1.size() != s2.size()) {
                // "insert" the missing character or equally
                // "remove" the wrong character
                if (*it_s2 == *std::next(it_s1, 1)) {
                    ++it_s1;
                } else {
                    return false;   
                }
            }
        }
    }
    return true;
}