Before and After Puzzle

medium hash table string sorting

Problem

Given a list of phrases, generate a list of "Before and After" puzzles. A puzzle is formed by joining two distinct phrases (at different indices) where the last word of the first phrase equals the first word of the second phrase. Merge them into one phrase by overlapping that shared word. Return the result with duplicate puzzles removed and sorted lexicographically.

Inputphrases = ["writing code", "code rocks"]

Output["writing code rocks"]

The last word of phrase 0 ("code") matches the first word of phrase 1 ("code"), so they merge into "writing code rocks".

phrases (one per line)

def before_and_after_puzzles(phrases):
    first = {}
    words = [p.split() for p in phrases]
    for j, w in enumerate(words):
        first.setdefault(w[0], []).append(j)
    result = set()
    for i, w in enumerate(words):
        for j in first.get(w[-1], []):
            if i != j:
                merged = w + words[j][1:]
                result.add(" ".join(merged))
    return sorted(result)

function beforeAndAfterPuzzles(phrases) {
  const words = phrases.map(p => p.split(" "));
  const first = new Map();
  words.forEach((w, j) => {
    if (!first.has(w[0])) first.set(w[0], []);
    first.get(w[0]).push(j);
  });
  const result = new Set();
  words.forEach((w, i) => {
    const last = w[w.length - 1];
    for (const j of first.get(last) || []) {
      if (i !== j) result.add([...w, ...words[j].slice(1)].join(" "));
    }
  });
  return [...result].sort();
}

class Solution {
    public List<String> beforeAndAfterPuzzles(String[] phrases) {
        String[][] words = new String[phrases.length][];
        Map<String, List<Integer>> first = new HashMap<>();
        for (int j = 0; j < phrases.length; j++) {
            words[j] = phrases[j].split(" ");
            first.computeIfAbsent(words[j][0], k -> new ArrayList<>()).add(j);
        }
        TreeSet<String> result = new TreeSet<>();
        for (int i = 0; i < words.length; i++) {
            String last = words[i][words[i].length - 1];
            for (int j : first.getOrDefault(last, List.of())) {
                if (i == j) continue;
                StringBuilder sb = new StringBuilder(phrases[i]);
                for (int k = 1; k < words[j].length; k++) sb.append(" ").append(words[j][k]);
                result.add(sb.toString());
            }
        }
        return new ArrayList<>(result);
    }
}

vector<string> beforeAndAfterPuzzles(vector<string>& phrases) {
    vector<vector<string>> words(phrases.size());
    unordered_map<string, vector<int>> first;
    for (int j = 0; j < (int)phrases.size(); j++) {
        stringstream ss(phrases[j]); string t;
        while (ss >> t) words[j].push_back(t);
        first[words[j][0]].push_back(j);
    }
    set<string> result;
    for (int i = 0; i < (int)words.size(); i++) {
        string last = words[i].back();
        for (int j : first[last]) {
            if (i == j) continue;
            string merged = phrases[i];
            for (int k = 1; k < (int)words[j].size(); k++) merged += " " + words[j][k];
            result.insert(merged);
        }
    }
    return vector<string>(result.begin(), result.end());
}

Explanation

We join two different phrases when the last word of one equals the first word of the other, overlapping that shared word. To avoid comparing every phrase against every other naively, we use a hash map keyed by first words.

Step one: for each phrase split into words, record its index under its first word in a map first. Now, given any word, we can instantly find all phrases that start with it.

Step two: for each phrase i, take its last word and look it up in the map. Every phrase j (with i != j) starting with that word is a valid partner. We merge by taking phrase i's words plus phrase j's words after the shared one: w + words[j][1:].

We collect merges in a set to drop duplicates, then sort the results lexicographically before returning.

Example: ["writing code", "code rocks"]. Phrase 0 ends with "code", which is the first word of phrase 1, so they merge into "writing code rocks".

Time: O(n² · L) Space: O(n · L)