# 1181. Before and After Puzzle

• Time: $O(n)$
• Space: $O(n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 class Solution { public: vector beforeAndAfterPuzzles(vector& phrases) { set ans; unordered_map> firstWordToLasts; unordered_map> lastWordToFirsts; for (const string& phrase : phrases) { const int firstSpaceIndex = phrase.find(' '); const int lastSpaceIndex = phrase.rfind(' '); // Index after firstWord. const int i = firstSpaceIndex == string::npos ? phrase.length() : firstSpaceIndex; // Index of lastWord. const int j = lastSpaceIndex == string::npos ? 0 : lastSpaceIndex + 1; const string firstWord = phrase.substr(0, i); const string lastWord = phrase.substr(j); // Concatenate phrase w/ last having the same firstWord. if (const auto it = firstWordToLasts.find(lastWord); it != cend(firstWordToLasts)) for (const string& last : it->second) ans.insert(phrase + last); // Concatenate first having the same lastWord w/ phrase. if (const auto it = lastWordToFirsts.find(firstWord); it != cend(lastWordToFirsts)) for (const string& first : it->second) ans.insert(first + phrase); // e.g. "a b c" -> {"a": " b c"} // "a" -> {"a": ""} firstWordToLasts[firstWord].insert(phrase.substr(i)); // e.g. "a b c" -> {"c": "a b "} // "a" -> {"a": ""} lastWordToFirsts[lastWord].insert(phrase.substr(0, j)); } return {begin(ans), end(ans)}; } };