Before and After Puzzle - Solution & Explanation
Problem Statement
Given a list of phrases, generate a list of Before and After puzzles.
A phrase is a string that consists of lowercase English letters and spaces only. No space appears in the start or the end of a phrase. There are no consecutive spaces in a phrase.
Before and After puzzles are phrases that are formed by merging two phrases where the last word of the first phrase is the same as the first word of the second phrase. Note that only the last word of the first phrase and the first word of the second phrase are merged in this process.
Return the Before and After puzzles that can be formed by every two phrases phrases[i] and phrases[j] where i != j. Note that the order of matching two phrases matters, we want to consider both orders.
You should return a list of distinct strings sorted lexicographically, after removing all duplicate phrases in the generated Before and After puzzles.
Example 1:
Input: phrases = ["writing code","code rocks"]
Output: ["writing code rocks"]
Example 2:
Input: phrases = ["mission statement","a quick bite to eat","a chip off the old block","chocolate bar","mission impossible","a man on a mission","block party","eat my words","bar of soap"]
Output: ["a chip off the old block party","a man on a mission impossible","a man on a mission statement","a quick bite to eat my words","chocolate bar of soap"]
Example 3:
Input: phrases = ["a","b","a"]
Output: ["a"]
Example 4:
Input: phrases = ["ab ba","ba ab","ab ba"]
Output: ["ab ba ab","ba ab ba"]
Constraints:
1 <= phrases.length <= 1001 <= phrases[i].length <= 100
Approach Overview
Problem Overview: You are given a list of phrases. If the last word of one phrase matches the first word of another, you can combine them into a new phrase without repeating the shared word. Generate all such combinations and return them sorted lexicographically with duplicates removed.
Approach 1: Brute Force Pair Comparison (O(n^2 * L) time, O(n * L) space)
Check every ordered pair of phrases. For each pair (i, j), split both phrases into words and compare the last word of phrases[i] with the first word of phrases[j]. When they match, build a new phrase by appending the second phrase without its first word. Store results in a set to remove duplicates, then sort the final list. This approach is straightforward but performs unnecessary comparisons between phrases that can never match.
The time cost comes from n^2 pair checks plus word extraction from each phrase. With many phrases, repeated string splitting becomes expensive. Still, it demonstrates the core idea clearly and is a useful baseline when reasoning about correctness.
Approach 2: Hash Table + Sorting (O(n^2 + r log r) time, O(n * L) space)
Instead of repeatedly scanning phrases, preprocess them using a hash table. Extract the first word of each phrase and map it to the phrase indices. Then iterate through each phrase, compute its last word, and use a constant-time hash lookup to find phrases whose first word matches that last word.
For every match, construct the merged phrase by concatenating the current phrase with the remainder of the second phrase (everything except its first word). Insert results into a set to eliminate duplicates caused by different index combinations producing the same phrase. This reduces unnecessary comparisons because only phrases with matching boundary words are considered.
After generating all combinations, convert the set into a list and sort it lexicographically using standard string sorting from the sorting toolkit. Phrase processing relies heavily on string manipulation, making this a practical exercise in string parsing and indexing.
Recommended for interviews: The hash table + sorting solution is the expected approach. Brute force proves you understand the merging rule, but the optimized version shows you can reduce unnecessary comparisons using a hash map keyed by the first word. Interviewers typically look for this transition from pairwise scanning to indexed lookup.
Solution
First, we traverse the phrases list, storing the first and last words of each phrase in the array ps, where ps[i][0] and ps[i][1] represent the first and last words of the ith phrase, respectively.
Next, we enumerate all (i, j), where i, j \in [0, n) and i neq j. If ps[i][1] = ps[j][0], then we can concatenate the ith phrase and the jth phrase to get a new phrase phrases[i] + phrases[j][len(ps[j][0]):], and add the new phrase to the hash table s.
Finally, we convert the hash table s into an array and sort it to get the answer.
The time complexity is O(n^2 times m times (log n + log m)), and the space complexity is O(n^2 times m). Here, n and m represent the length of the phrases array and the average length of each phrase, respectively.
Code
Python
Java
C++
Go
TypeScript
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Pair Comparison | O(n^2 * L) | O(n * L) | Small input sizes or when quickly validating the merging logic |
| Hash Table + Sorting | O(n^2 + r log r) | O(n * L) | General case; reduces unnecessary comparisons using hash lookups |
Video Solution
1181. Before and After Puzzle - Week 4/5 Leetcode August Challenge • Programming Live with Larry • 251 views views
Watch 2 more video solutions →Frequently Asked Questions
Is Before and After Puzzle easy or hard?
Before and After Puzzle Python/Java solution
How to solve Before and After Puzzle in O(n)?
What is the best approach for Before and After Puzzle?
Is Before and After Puzzle asked at Google/Amazon/Meta?
What data structure is used in Before and After Puzzle?
What is the time complexity of Before and After Puzzle?
Ready to solve this problem?
Practice Before and After Puzzle with our built-in code editor and test cases.
Practice on FleetCode