Test whether the edit-distance of two strings is at most 1

Question

There are three types of edits that can be performed on strings: insert a character, remove a character, or replace a character.

EXAMPLES:

pale, ple returns true

pales, pale returns true

pale, bale returns true

pale, bake returns false

My solutions seems to work for any case I could think of (like ("", "s") but I feel like I'm checking conditions too much in it (mainly my final if/else statement had to be tacked on when I saw my solution wouldn't work for ("pales", "pale"))

bool oneAway(string s1, string s2)
{
    //loop through smaller string size
    decltype(s1.size()) size = (s1.size() < s2.size()) ? s1.size() : s2.size();

    for (decltype(s1.size()) i = 0; i < size; ++i)
    {
        if (s1[i] != s2[i])
        {
            string temp1 = s1.substr(i + 1);
            string temp2 = s2.substr(i + 1);

            //if rest of the string is equal we do 1 replacement.
            if (temp1 == temp2)
            {
                s1[i] = s2[i];
                break;
            }

            //otherwise we will try to insert or remove a character
            else
            {
                if (s1.size() < s2.size())
                {
                    s1.insert(i, 1, s2[i]);
                    break;
                }
                else
                {
                    s1.erase(i, 1);
                    break;
                }
            }
        }
    }

    //check equality
    if (s1 == s2)
        return true;

    //otherwise try to erase last character in s1 and check again (since for loop may not check this character if s2 was smaller string size)
    else
    {
        s1.erase(s1.size() - 1, 1);
        if (s1 == s2)
            return true;
    }
    return false;

}

This question is from the book "Cracking the Code Interview" by Gayle McDowell.

Answer 1

1. It looks like you either imported std::string or the whole standard namespace into the global namespace.
   It's ok to do the former in implementation-files, though I would desist as it doesn't gain you all that much in brevity.
   If it's the latter, read "Why is “using namespace std;” considered bad practice?" and change it.

2. Avoid allocating memory. Doing so is slow and can fail. That means accepting the arguments by constant reference, not using temporary copies, and not modifying the arguments.
   If you had C++17, it would mean changing to std::string_view for the added flexibility.

3. Prefer using auto to a more complicated expression using decltype. It's less error-prone, more readable, and also shorter.

4. <algorithm> contains std::min(). Using that is more readable, shorter and no less efficient than writing it out using the conditional-operator.

5. Did you test ("abc", "b")? That's two deletions edit-distance, but will be accepted anyway.

6. Keep your line-length reasonable. Horizontal scrolling kills readability.

Using all that, but staying true to C++11:

#include <string>
#include <algorithm>

bool oneAway(const std::string& a, const std::string& b) noexcept {
    if (a.size() > b.size())
        return oneAway(b, a);
    if (b.size() - a.size() > 1) // No need to look further, pure optimization
        return false;
    auto begin = std::mismatch(a.begin(), a.end(), b.begin());
    using reverse_it = decltype(a.rbegin()); // std::make_reverse_iterator is C++14
    auto end = std::mismatch(a.rbegin(), reverse_it(begin.first), b.rbegin());
    return end.second.base() - begin.second < 2;
}

And for testing:

#include "one_away.h"
#include <iostream>
#include <cstdlib>

static bool do_test(const std::string& a, const std::string& b, bool expected) {
    bool r = oneAway(a, b);
    std::cout << (r == expected ? "[OK] " : "[FAIL] ")
        << std::boolalpha << r << " \"" << a << "\" \"" << b << \"\n";
    return r == expected;
}

static bool test(const std::string& a, const std::string& b = a, bool expected = true) {
    bool r = do_test(a, b, expected);
    if (a != b)
        r &= do_test(b, a, expected);
    return r;
}

int main() {
    bool r = test("");
    r &= test("abc");
    r &= test("pale", "ple");
    r &= test("pales", "pale");
    r &= test("pale", "bale");
    r &= test("pale", "bake", false);
    r &= test("abc", "b", false);
    std::cout << (r ? "[OK]\n" : "[FAIL]\n");
    return r ? 0 : EXIT_FAILURE;
}

Answer 2

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;
}

---

Edit

Here a take at @Deduplicators suggestion, I didnt see that std::mismatch returns a pair of iterators, so it is really nice and doesnt even require reverse iterators

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 res = std::mismatch(s2.begin(), s2.end(), s1.begin());
    if (res.first== s2.end()) {
        return true;
    }

    res = std::mismatch(res.first, s2.end(), ++res.second);
    if (res.first== s2.end()) {
        return true;
    }
    return false;
}