Problem Breakdown
The problem requires generating “Before and After” puzzles from two phrases. A valid puzzle is formed when the last word of phrase i matches the first word of phrase j. The merging process involves concatenating them while ensuring the common boundary word appears only once (dropping it from the end of the first phrase). We must consider all pairs where . Finally, we return a list of distinct strings sorted lexicographically.
Intuition
Given the constraint phrases.length <= 100, an brute-force approach is computationally feasible ( operations). We can iterate through every pair to check for boundary matches. To handle the requirement of returning distinct strings efficiently without duplicates during construction, a Python set is ideal because it automatically handles uniqueness and allows average time complexity lookups/insertions (though insertion here happens only on match). Sorting at the very end ensures lexicographical order as required.
Approach
- Pre-processing: To optimize efficiency within the nested loops, split all phrases into lists of words upfront before entering the pair iteration logic. This avoids redundant string splitting operations inside the inner loop.
- Pair Iteration: Iterate through every phrase index
i(outer loop) and every phrase indexj(inner loop). - Boundary Check: For each pair, check if the last word of
phrases[i]matches the first word ofphrases[j]. Skip pairs where . - Merge Construction: If a match is found:
- Take all words from phrase
iexcept the last one ([:-1]). - Append all words from phrase
j(including its first word). - Join these combined words with spaces to form the puzzle string.
- Take all words from phrase
- Storage and Return: Add each valid puzzle string to a set. After checking all pairs, convert the set to a list and sort it lexicographically before returning.
Complexity Analysis
- Time: , where is the number of phrases and is the maximum length of a phrase (for word splitting/joining). The dominant factor is checking all pairs (), with string operations proportional to phrase length. Sorting takes where is the number of unique results, which is negligible compared to pair generation for small inputs but included in worst-case analysis.
- Space: . We store pre-split words (), plus the set of resulting puzzles ().
Solution
from typing import List, Set
class Solution:
def beforeAndAfterPuzzles(self, phrases: List[str]) -> List[str]:
# Pre-process all phrases into word lists to avoid repeated splitting in loops
phrase_words = [p.split() for p in phrases]
result_set: Set[str] = set()
n = len(phrases)
for i in range(n):
last_word_i = phrase_words[i][-1]
# Optimization: Cache the words list of j to avoid repeated access overhead?
# Actually, accessing list is O(1). Splitting was removed.
for j in range(n):
if i == j:
continue
first_word_j = phrase_words[j][0]
# Check boundary condition: last word of i vs first word of j
if last_word_i == first_word_j:
# Construct the merged puzzle.
# We drop the last word from 'i' (the common one) and keep all words in 'j'.
combined_words = phrase_words[i][:-1] + phrase_words[j]
result_set.add(' '.join(combined_words))
return sorted(list(result_set))
Edge Cases Handled
- No Matches: If no pairs satisfy the condition,
result_setremains empty; returns an empty list. - Identical Phrases at Different Indices: Example 3 (
["a", "b", "a"]) correctly treats indices as distinct entities ( vs ), allowing a match on content even if strings are identical, while preventing self-matching via theif i == j: continuecheck. - Single Word Phrases: Logic holds (e.g., dropping last word from single-word phrase results in empty list before appending second phrase).
- Duplicate Results: The use of a Python
setensures that if multiple pairs generate the exact same puzzle string, only one instance is kept in the final output.