Problem Explanation

This problem is about generating a list of unique Before and After puzzles from a list of phrases. A Before and After puzzle is generated by combining two phrases such that the last word of the first phrase is the same as the first word of the second phrase.

For example, if we have the phrases "writing code" and "code rocks", we can merge them into "writing code rocks". We are required to generate all possible unique puzzles and sort them lexicographically.

It's also important to note that the order of merging matters i.e., you can merge phrase1 with phrase2 and also phrase2 with phrase1 as long as the merge is valid.

Approach

The solution leverages hash maps and a set to solve the problem. It utilizes two hash maps; firstWordToLasts that maps the first word of a phrase to the rest of the phrase and lastWordToFirsts that maps the last word of a phrase to the entire phrase minus the last word.

For every phrase in the phrases list, the solution does the following:

1. Extracts the first and last word and their respective sections of the phrase.
2. Checks if the last word exists in firstWordToLasts and adds all valid merges to ans set.
3. Checks if the first word exists in lastWordToFirsts and adds all valid merges to ans set.
4. Adds the first word and rest of the phrase to firstWordToLasts map.
5. Adds the last word and the first part of the phrase to lastWordToFirsts map.

Finally, the solution returns the phrases in ans set as they are already unique and sorted due to the properties of a set.

Walkthrough

Let's take an example where phrases = ["writing code","code rocks"]. Here is how the solution would work:

1. For the first phrase "writing code", firstWordToLasts would be {"writing": " code"} and lastWordToFirsts would be {"code": "writing "}.
2. For the second phrase "code rocks", the solution would find code in firstWordToLasts and merge the phrases into "writing code rocks" and add it to ans.
3. Finally, return the ans which contains ["writing code rocks"].

C++ Solution

1
2c++
3class Solution {
4 public:
5  vector<string> beforeAndAfterPuzzles(vector<string>& phrases) {
6    set<string> ans;
7    unordered_map<string, set<string>> firstWordToLasts;
8    unordered_map<string, set<string>> lastWordToFirsts;
9
10    for (const string& phrase : phrases) {
11      const int firstSpaceIndex = phrase.find(' ');
12      const int lastSpaceIndex = phrase.rfind(' ');
13      const int i = firstSpaceIndex == string::npos ? phrase.length() : firstSpaceIndex;
14      const int j = lastSpaceIndex == string::npos ? 0 : lastSpaceIndex + 1;
15
16      const string firstWord = phrase.substr(0, i);
17      const string lastWord = phrase.substr(j);
18
19      if (const auto it = firstWordToLasts.find(lastWord); it != cend(firstWordToLasts))
20        for (const string& last : it->second)
21          ans.insert(phrase + last);
22
23      if (const auto it = lastWordToFirsts.find(firstWord); it != cend(lastWordToFirsts))
24        for (const string& first : it->second)
25          ans.insert(first + phrase);
26
27      firstWordToLasts[firstWord].insert(phrase.substr(i));
28      lastWordToFirsts[lastWord].insert(phrase.substr(0, j));
29    }
30
31    return {begin(ans), end(ans)};
32  }
33};

Note

Java, JavaScript, Python and C# versions of the code aren't provided due to the time constraint.# Python Solution

1
2python
3from collections import defaultdict
4
5def beforeAndAfterPuzzles(phrases):
6    firsts = defaultdict(list)
7    lasts = defaultdict(list)
8    ans = set()
9
10    for phrase in phrases:
11        words = phrase.split()
12        # get first and last word in all phrases
13        first, last = words[0], words[-1]
14        # check able to merge in both ways.
15        for s in firsts[last]: 
16            ans.add(s + " " + " ".join(words[1:]))
17        for s in lasts[first]:
18            ans.add(" ".join(words[:-1]) + " " +s)
19        # prepare for next merge.
20        firsts[first].append(phrase)
21        lasts[last].append(phrase)
22    return sorted(ans)

JavaScript Solution

1
2javascript
3function beforeAndAfterPuzzles(phrases) {
4    const firsts = new Map(), lasts = new Map(), ans = new Set();
5    
6    for (const phrase of phrases) {
7        const words = phrase.split(" ");
8        const [first, last] = [words[0], words[words.length - 1]];
9
10        (firsts.get(last) || []).map(s => ans.add(s + " " + words.slice(1).join(" ")));
11        (lasts.get(first) || []).map(s => ans.add(words.slice(0, -1).join(" ") + " " + s));
12        
13        firsts.set(first, (firsts.get(first) || []).concat(phrase));
14        lasts.set(last, (lasts.get(last) || []).concat(phrase));
15    }
16    
17    return Array.from(ans).sort();
18}

Java Solution

1
2java
3class Solution {
4    public List<String> beforeAndAfterPuzzles(String[] phrases) {
5        Map<String, List<String>> firsts = new HashMap<>(), lasts = new HashMap<>();
6        Set<String> ans = new HashSet<>();
7        
8        for (String phrase : phrases) {
9            String[] words = phrase.split(" ");
10            String first = words[0], last = words[words.length - 1];
11
12            if (firsts.containsKey(last)) {
13                for (String s : firsts.get(last)) {
14                    ans.add(s + " " + String.join(" ", Arrays.copyOfRange(words, 1, words.length)));
15                }
16            }
17            if (lasts.containsKey(first)) {
18                for (String s : lasts.get(first)) {
19                    ans.add(String.join(" ", Arrays.copyOfRange(words, 0, words.length - 1)) + " " + s);
20                }
21            }
22            firsts.computeIfAbsent(first, k -> new ArrayList<>()).add(phrase);
23            lasts.computeIfAbsent(last, k -> new ArrayList<>()).add(phrase);
24        }
25
26        List<String> res = new ArrayList<>(ans);
27        Collections.sort(res);
28        return res;
29    }
30}

In all these solutions, we are storing the first and last element of a string in a Map to do fast lookups and generate the result. The final result (ans) is a Set for uniqueness and sorting purposes.