/* * Connecting words * * Write a function that connects each previous * word to the next word by the shared letters. * Return the resulting string * (removing duplicate characters in the * overlap) * and the minimum number of shared letters * across * all pairs of strings. * * Example: * * join(["oven", "envier", "erase", "serious"]) * ➞ ["ovenvieraserious", 2] * * join(["move", "over", "very"]) * ➞ ["movery", 3] * * join(["to", "ops", "psy", "syllable"]) * ➞ ["topsyllable", 1] * * "to" and "ops" share "o" (1) * "ops" and "psy" share "ps" (2) * "psy" and "syllable" share "sy" (2) * the minimum overlap is 1 * * join(["aaa", "bbb", "ccc", "ddd"]) * ➞ ["aaabbbcccddd", 0] * * Notes: * * More specifically, look at the overlap * between the previous words ending letters * and the next word's beginning letters. https://www.sololearn.com/post/239180/?ref=app */ #include #include #include #include using namespace std; auto Transform(vector vstr) { size_t mino = 0x3f3f3f3f; string res{vstr.at(0)}; for(auto it{next(vstr.begin())}; it!=vstr.end(); ++it) { size_t len = min(it->size(),res.size()); size_t j {len}; for(; j>0; --j) if(res.substr(res.size()-j) == it->substr(0,j)) break; if(j < mino) mino = j; res += it->substr(j); } return make_pair(res, mino); } int main(int argc, char *argv[]) { auto Print = [](auto const& in){ cout << "["; for(auto&& str : in ) cout << "\"" << str << "\"" << ','; cout << ']' << '\n'; }; for(auto&& in : vector>{ {"move", "over", "very"}, {"aaa","bbb"}, {"over", "erlang", "g","gum"}, {"erase", "set", "code"}, {"to","ops","psy","syllable"}, {"oven","envier","erase","serious"}, {"","abc"}}) { Print(in); auto const&[res, len] = Transform(in); cout << "result = {" << res << ',' << len << "}\n\n"; } }

[Challenge] Connecting Words.cpp