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 \leq$ phrases.length $\leq 100$

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

The key idea is to use a hash map to efficiently match the last word of one phrase with the first word of another. We build a mapping from each phrase’s first word to the indices where that phrase appears. Then, for every phrase, we extract its last word and look it up in the hash map to find all candidate phrases that start with that same word. For each valid pair (where the two phrases are at different indices), we merge them by appending everything after the shared first word of the second phrase onto the first phrase. We collect all merged results in a set to eliminate duplicates, and finally return the sorted list.

Now, let’s look at the solution steps below:

1. Initialize a hash map firstWordMap using a defaultdict(list). Iterate over all phrases with their indices, split each phrase to extract its first word, and store the index in firstWordMap under that first word as the key.

2. Initialize an empty set resultSet to store distinct merged puzzles.

3. Iterate over each phrase with index i in phrases:

   1. Split the phrase and extract its last word, stored as lastWord.

   2. Check if lastWord exists as a key in firstWordMap. If it does, iterate over every index j stored in firstWordMap[lastWord].

      1. If i $\neq$ j (ensuring we do not pair a phrase with itself by index), compute the merged result. The rest of the second phrase restOfSecond is obtained by slicing phrases[j] starting from the length of lastWord, which removes the shared word from the beginning of the second phrase. The merged string is phrase + restOfSecond.

      2. Add the merged string to resultSet.

4. Convert resultSet to a sorted list and return it. Sorting ensures the output is in lexicographical order.

Let’s look at the following illustration to get a better understanding of the solution:

Let’s look at the code for ...