cxx17/cc15.cc

62 lines
1.5 KiB
C++

// Determine if a string is one edit away from another.
#define CATCH_CONFIG_MAIN
#include <catch.hpp>
#include <cassert>
#include <experimental/string_view>
#include <range/v3/all.hpp>
#include <string>
#include <unordered_map>
using namespace ranges;
using string_view = std::experimental::string_view;
bool is_insert(string_view lhs, string_view rhs) {
assert(lhs.length() < rhs.length());
auto lh = lhs.cbegin();
auto rh = rhs.cbegin();
// Skip the matching characters.
for (; *lh == *rh && lh != lhs.cend();) {
lh++;
rh++;
}
// Skip the inserted character.
rh++;
// Rest should match.
return string_view(lh, lhs.cend() - lh) == string_view(rh, rhs.cend() - rh);
}
bool one_edit(string_view lhs, string_view rhs) {
if (lhs.length() == rhs.length()) {
// Possible change.
int diffs = 0;
for (const auto& pair : view::zip(lhs, rhs)) {
if (pair.first != pair.second) {
diffs++;
}
}
return diffs <= 1;
} else if (lhs.length() < rhs.length()) {
return is_insert(lhs, rhs);
} else if (lhs.length() > rhs.length()) {
return is_insert(rhs, lhs);
}
return false;
}
TEST_CASE("cc15", "edits") {
CHECK(is_insert("", "a") == true);
CHECK(is_insert("a", "ab") == true);
CHECK(is_insert("abc", "abdc") == true);
CHECK(is_insert("bc", "abc") == true);
CHECK(one_edit("pale", "ple") == true);
CHECK(one_edit("pales", "pale") == true);
CHECK(one_edit("pale", "pales") == true);
CHECK(one_edit("pale", "bale") == true);
CHECK(one_edit("pale", "bake") == false);
}