The task is to write one_edit_apart function that determines is it possible to make two given strings equal by replacing, adding or removing one symbol. The equal strings are considered to be equal, for example:
one_edit_apart("cat", "at") == true
one_edit_apart("cat", "cats") == true
one_edit_apart("cat", "cast") == true
one_edit_apart("cast", "cats") == false
one_edit_apart("cat", "cut") == true
one_edit_apart("cat", "dog") == false
The task is trivial, but Yandex interviewers require all the calculation to be done exactly in their inline editor without debugging and compiling and they do not accept the solution until it works for all possible input. The obvious solution is to truncate equal heads and equal tails and check if the lengths of remaining strings are not greater than 1, but if you forgot to handle the case when heads and tails intersect (with “a” and “aa”, for example) they will say “ooops…., you did a newbie mistake that 1-st year students usually do” and if this all takes more than 40 minutes you fail to pass the test. Below I provided the source code they are most likely to accept:
#include <iostream>
#include <string>
#include <cmath>
#include <cassert>
bool one_edit_apart(const std::string& s1, const std::string& s2)
{
size_t head_index = 0;
const size_t min_length = std::min(s1.length(), s2.length());
while (head_index != min_length && s1[head_index] == s2[head_index])
{
++head_index;
}
//The strings are equal.
if (s1.length() == s2.length() && head_index == s1.length())
{
return true;
}
size_t tail_offset = 0;
//There is also a case when the head and tail intersect, for example "a", "aa".
while (tail_offset + head_index != min_length && *(s1.rbegin() + tail_offset) == *(s2.rbegin() + tail_offset))
{
++tail_offset;
}
const size_t equal_length = tail_offset + head_index;
assert(equal_length <= min_length);
const auto diff1 = s1.length() - equal_length;
const auto diff2 = s2.length() - equal_length;
return diff1 <= 1 && diff2 <= 1;
}
void ensure(const std::string& s1, const std::string& s2, bool result)
{
const bool actual = one_edit_apart(s1, s2);
if (actual != result)
{
std::cout << s1 << ", " << s2 << ", expected: " << result << ", actual: " << actual << std::endl;
}
}
int main()
{
ensure("cat", "at", true);
ensure("cat", "cats", true);
ensure("cat", "cast", true);
ensure("cast", "cats", false);
ensure("cat", "cut", true);
ensure("cat", "dog", false);
ensure("cast", "caxt", true);
ensure("a", "aa", true);
ensure("a", "a", true);
ensure("aa", "aa", true);
ensure("aaa", "aa", true);
ensure("aaab", "aab", true);
return 0;
}
