53 lines
1.5 KiB
C++
53 lines
1.5 KiB
C++
// Test if a string is a rotation of another.
|
|
|
|
#define CATCH_CONFIG_MAIN
|
|
#include <catch.hpp>
|
|
|
|
#include <fmt/format.h>
|
|
#include <experimental/string_view>
|
|
#include <string>
|
|
#include <unordered_set>
|
|
|
|
using string_view = std::experimental::string_view;
|
|
|
|
bool is_rotation(string_view lhs, string_view rhs) {
|
|
// Confirm using one call to isSubstring.
|
|
// Facts:
|
|
// Must be the same length.
|
|
// Must have the same letters and counts.
|
|
// Adjacents must be the same.
|
|
|
|
// Brute force version.
|
|
for (auto it = lhs.cbegin(); it != lhs.cend(); it++) {
|
|
std::string rotated{it, size_t(lhs.cend() - it)};
|
|
rotated += std::string{lhs.cbegin(), size_t(it - lhs.cbegin())};
|
|
|
|
if (rotated == rhs) {
|
|
return true;
|
|
}
|
|
}
|
|
return false;
|
|
}
|
|
|
|
bool is_rotation_2(const std::string& lhs, const std::string& rhs) {
|
|
// Clever version: if lhs is a rotation of rhs, then lhs is a
|
|
// substring of rhs+rhs.
|
|
if (lhs.length() != rhs.length()) {
|
|
return false;
|
|
}
|
|
|
|
return (lhs + lhs).find(rhs) != std::string::npos;
|
|
}
|
|
|
|
TEST_CASE("cc19", "rotate") {
|
|
CHECK(is_rotation("waterbottle", "waterbottle") == true);
|
|
CHECK(is_rotation("waterbottle", "erbottlewat") == true);
|
|
CHECK(is_rotation("waterbottle", "erbotltewat") == false);
|
|
CHECK(is_rotation("waterbottle1", "erbottlewat1") == false);
|
|
|
|
CHECK(is_rotation_2("waterbottle", "waterbottle") == true);
|
|
CHECK(is_rotation_2("waterbottle", "erbottlewat") == true);
|
|
CHECK(is_rotation_2("waterbottle", "erbotltewat") == false);
|
|
CHECK(is_rotation_2("waterbottle1", "erbottlewat1") == false);
|
|
}
|