Search⌘ K
AI Features
Home
Courses
Grokking the Coding Interview Patterns in C++

Solution: Before and After Puzzle

Explore how to solve the Before and After puzzle by efficiently merging phrases with matching words using hash maps. Understand building mappings for phrase words, eliminating duplicates, and sorting results. Gain hands-on insight into solving this common coding interview problem involving strings and hash map techniques.

We'll cover the following...

Statement

Given a list of strings phrases, generate all possible Before and After puzzles.

Each phrase is a string composed of lowercase English letters and spaces. No phrase begins or ends with a space, and no phrase contains consecutive spaces.

A Before and After puzzle is formed by merging two phrases such that the last word of the first phrase is identical to the first word of the second phrase. When merging, this shared word appears only once in the resulting combined phrase.

For every pair of indices i and j where i ≠\neq j, consider forming a Before and After puzzle by using phrases[i] as the first phrase and phrases[j] as the second phrase. Since the order of the two phrases matters, both orderings of each pair should be considered.

Return a list of all distinct Before and After puzzles that can be formed, sorted in lexicographical order.

Note: Duplicate phrases may exist in the input. Pairs are determined by index, not by value, meaning two phrases at different indices can be paired even if they have the same content. However, duplicate results in the output should be removed.

Constraints:

  • 1≤1 \leq phrases.length ≤100\leq 100

  • 1≤1 \leq phrases[i].length ≤100\leq 100 ...