5
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ May want to look at Levenshtein distance: en.wikipedia.org/wiki/Levenshtein_distance ... or more generally the Edit distance: en.wikipedia.org/wiki/Edit_distance \$\endgroup\$ – Chris Kushnir Jul 14 '17 at 23:01
  • \$\begingroup\$ As an alternative algorithm, you might want to find the first and last positions where the two strings differ (using std::mismatch with the forward and reverse iterators, respectively). It's a simple comparison between the results to spot that you've reached the same position in one string or the other. The only catch is that forward iterators aren't directly comparable to the reverse iterators, so you need to use std::make_reverse_iterator(), or dereference and compare by identity (&*it1 == &*it2). Or use base(). \$\endgroup\$ – Toby Speight Jul 17 '17 at 8:32
5
\$\begingroup\$
  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;
}
\$\endgroup\$
  • \$\begingroup\$ oh I see my error you pointed out in your number 5 point. I changed my code so I pass in a constant reference and use two temp strings that I can modify (then the last else statement just checks the parameter value feels hacky but works). I will definitely look into std::string_view as I'm not familiar with it. \$\endgroup\$ – Eango Jul 14 '17 at 23:32
  • \$\begingroup\$ Thanks for providing how you would test it as well. Really helpful stuff. I definitely understand the code but I could never come up with it on my own. Guess I just got to practice my std algorithms more. \$\endgroup\$ – Eango Jul 19 '17 at 3:55
1
\$\begingroup\$

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;
}
\$\endgroup\$
  • \$\begingroup\$ That can be written nicer even restricted to C++11. \$\endgroup\$ – Deduplicator Jul 17 '17 at 14:12
  • \$\begingroup\$ I thought about using std::missmatch, however the problem is, that you want to increment both iterators, which most std algorithms simply dont do. In that case you would have to work with stuff like std::next(s1.begin(), std::distance(s2.begin(), missmatch)) which is not really better \$\endgroup\$ – miscco Jul 17 '17 at 19:27
  • \$\begingroup\$ Not really, mismatch from start, mismatch from end using reverse-iterators, examine the part between. See my post. \$\endgroup\$ – Deduplicator Jul 17 '17 at 19:38
  • \$\begingroup\$ Yeah, it turns out one just has to read the manual .. std::mismatch returns a pair of iterators so you can simply start from the result again \$\endgroup\$ – miscco Jul 17 '17 at 20:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.