63 lines
1.5 KiB
C++
63 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);
|
|
}
|