Want Help Cracking FAANG?

(Then click this)

 ×
Back to Question Bank

1181. Before and After Puzzle - Leetcode Solution

Problem Description

The "Before and After Puzzle" problem asks you to combine phrases from a given list in a specific way. You are given a list of strings called phrases. Your task is to find all unique phrases that can be formed by concatenating two different phrases from the list, such that the last word of the first phrase is the same as the first word of the second phrase. The resulting phrase should not repeat the shared word.

Constraints:
  • Each phrase is a non-empty string of words separated by single spaces.
  • Do not use the same phrase twice in a combination (i.e., indices must be different).
  • Return all unique resulting phrases in lexicographical order.

Example:
Input: ["writing code", "code rocks"]
Output: ["writing code rocks"]
Explanation: The last word of "writing code" is "code", which matches the first word of "code rocks". So we can combine them into "writing code rocks".

Thought Process

At first glance, the problem seems to suggest trying every possible pair of phrases and checking if the last word of the first matches the first word of the second. This brute-force method is simple but potentially inefficient for large inputs. To optimize, we want a way to quickly find all phrases that start with a particular word, and all phrases that end with a particular word. This suggests using a mapping (like a hash map or dictionary) from a word to the indices of phrases that start with that word. Then, for each phrase, we can look up all possible phrases that can follow it, instead of checking every pair. The key is to:
  • Efficiently extract the first and last words of each phrase.
  • Quickly match and combine phrases without duplicates.
  • Return the results in sorted order and ensure uniqueness.

Solution Approach

Let's break down the optimized solution step by step:
  1. Preprocessing: For each phrase, extract its first and last word.
    • Store a mapping from first word to a list of phrase indices that start with that word.
  2. Matching Phrases: For each phrase:
    • Get its last word.
    • Look up all phrase indices whose first word matches this last word.
    • For each match, if the indices are different, combine the two phrases, omitting the duplicate word at the junction.
  3. Combine Phrases: When combining, take the full first phrase, then append the second phrase starting from its second word onwards (to avoid repeating the shared word).
  4. Deduplicate and Sort: Use a set to store results and finally return them sorted lexicographically.
Why this works: Using a map allows us to find all valid continuations for a phrase in O(1) time per candidate, instead of scanning the entire list each time. This greatly reduces time complexity.

Example Walkthrough

Let's use the example input: ["writing code", "code rocks", "rocks and rolls", "code writing"]
  1. Extract first and last words:
    • "writing code": first="writing", last="code"
    • "code rocks": first="code", last="rocks"
    • "rocks and rolls": first="rocks", last="rolls"
    • "code writing": first="code", last="writing"
  2. Build first-word map:
    • "writing": [0]
    • "code": [1, 3]
    • "rocks": [2]
  3. For each phrase, look for matches:
    • "writing code" (last="code"):
      • Find phrases starting with "code": indices 1 and 3
      • Index 1: "code rocks" → combine: "writing code rocks"
      • Index 3: "code writing" → combine: "writing code writing"
    • "code rocks" (last="rocks"):
      • Find phrases starting with "rocks": index 2
      • Index 2: "rocks and rolls" → combine: "code rocks and rolls"
    • "rocks and rolls" (last="rolls"): no phrase starts with "rolls"
    • "code writing" (last="writing"):
      • Find phrases starting with "writing": index 0
      • Index 0: "writing code" → combine: "code writing code"
  4. Result set:
    • "writing code rocks"
    • "writing code writing"
    • "code rocks and rolls"
    • "code writing code"
    After deduplication and sorting: ["code rocks and rolls", "code writing code", "writing code rocks", "writing code writing"]

Time and Space Complexity

  • Brute-force approach:
    • Try every ordered pair of phrases: O(N2) where N is the number of phrases.
    • For each pair, extract the first and last words (O(L) where L is average phrase length).
    • Total: O(N2 * L)
  • Optimized approach:
    • Building the map: O(N * L)
    • For each phrase, look up matching phrases in O(1) (amortized) per candidate, and combine in O(L).
    • Still worst-case O(N2 * L) if all phrases can be combined, but in practice much faster due to skipping non-matching pairs.
    • Space: O(N * L) for storing phrases and the map.

Summary

The "Before and After Puzzle" problem challenges you to efficiently combine phrases based on overlapping words. By mapping the first words to phrase indices, we can quickly find valid continuations for each phrase, avoiding unnecessary checks and duplicates. The approach balances clarity and efficiency, leveraging data structures like dictionaries and sets. The result is a solution that is both easy to understand and performant, especially compared to brute-force.

Code Implementation

from collections import defaultdict

class Solution:
    def beforeAndAfterPuzzles(self, phrases):
        first_word_map = defaultdict(list)
        n = len(phrases)
        for i, phrase in enumerate(phrases):
            first = phrase.split()[0]
            first_word_map[first].append(i)

        res = set()
        for i, phrase in enumerate(phrases):
            words = phrase.split()
            last = words[-1]
            if last in first_word_map:
                for j in first_word_map[last]:
                    if i == j:
                        continue
                    # Combine phrase i and j, omitting the duplicate word
                    combined = phrase + phrases[j][len(last):]
                    res.add(combined.strip())
        return sorted(res)
      
#include <vector>
#include <string>
#include <unordered_map>
#include <set>
#include <algorithm>
using namespace std;

class Solution {
public:
    vector<string> beforeAndAfterPuzzles(vector<string>& phrases) {
        unordered_map<string, vector<int>> first_word_map;
        int n = phrases.size();
        for (int i = 0; i < n; ++i) {
            string first = phrases[i].substr(0, phrases[i].find(' '));
            first_word_map[first].push_back(i);
        }
        set<string> res;
        for (int i = 0; i < n; ++i) {
            string phrase = phrases[i];
            size_t pos = phrase.rfind(' ');
            string last = (pos == string::npos) ? phrase : phrase.substr(pos + 1);
            if (first_word_map.count(last)) {
                for (int j : first_word_map[last]) {
                    if (i == j) continue;
                    string to_add = phrase;
                    string tail = phrases[j].substr(last.length());
                    if (!tail.empty() && tail[0] == ' ') tail = tail.substr(1);
                    if (!tail.empty()) to_add += " " + tail;
                    res.insert(to_add);
                }
            }
        }
        return vector<string>(res.begin(), res.end());
    }
};
      
import java.util.*;

class Solution {
    public List<String> beforeAndAfterPuzzles(String[] phrases) {
        Map<String, List<Integer>> firstWordMap = new HashMap<>();
        int n = phrases.length;
        for (int i = 0; i < n; ++i) {
            String first = phrases[i].split(" ")[0];
            firstWordMap.computeIfAbsent(first, k -> new ArrayList<>()).add(i);
        }
        Set<String> res = new TreeSet<>();
        for (int i = 0; i < n; ++i) {
            String[] words = phrases[i].split(" ");
            String last = words[words.length - 1];
            if (firstWordMap.containsKey(last)) {
                for (int j : firstWordMap.get(last)) {
                    if (i == j) continue;
                    String tail = phrases[j].substring(last.length());
                    String combined = phrases[i] + tail;
                    res.add(combined.trim());
                }
            }
        }
        return new ArrayList<>(res);
    }
}
      
/**
 * @param {string[]} phrases
 * @return {string[]}
 */
var beforeAndAfterPuzzles = function(phrases) {
    const firstWordMap = {};
    for (let i = 0; i < phrases.length; ++i) {
        const first = phrases[i].split(' ')[0];
        if (!firstWordMap[first]) firstWordMap[first] = [];
        firstWordMap[first].push(i);
    }
    const res = new Set();
    for (let i = 0; i < phrases.length; ++i) {
        const words = phrases[i].split(' ');
        const last = words[words.length - 1];
        if (firstWordMap[last]) {
            for (let j of firstWordMap[last]) {
                if (i === j) continue;
                const tail = phrases[j].substring(last.length);
                let combined = phrases[i] + tail;
                res.add(combined.trim());
            }
        }
    }
    return Array.from(res).sort();
};