We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Before and After Puzzle

Number: 1132

Difficulty: Medium

Paid? Yes

Companies: Clutter

Problem Description

Given a list of phrases, generate a list of Before and After puzzles. A puzzle is formed by merging two phrases where the last word of the first phrase is the same as the first word of the second phrase. The merged phrase is created by concatenating the two phrases but without repeating the common word. All valid pairs (with distinct indices and both orders) should be considered and the final list of puzzles must be distinct and sorted lexicographically.

Key Insights

  • Extract the first and last word from each phrase.
  • For every pair of phrases (i ≠ j), check if the last word of phrase[i] matches the first word of phrase[j].
  • Merge the phrases by concatenating phrase[i] with phrase[j] (omitting the duplicate word at the start of phrase[j]).
  • Use a set to automatically handle duplicate merged phrases.
  • Finally, sort the set of results lexicographically before returning.

Space and Time Complexity

Time Complexity: O(n^2 * L) where n is the number of phrases and L is the average length of a phrase (due to splitting and concatenation). Space Complexity: O(u) where u is the number of unique puzzles stored, with additional O(n) space for storing first and last words.

Solution

The approach involves pre-processing each phrase to extract its first and last word. Then, using two nested loops, we iterate over all pairs of phrases (ensuring i ≠ j) and check if the last word of the first phrase is equal to the first word of the second. When a match is found, the two phrases are merged by taking the full first phrase and appending the second phrase starting just after its first word. This merged string is added to a set to guarantee uniqueness. Finally, the set is converted to a sorted list which is returned as the result. This method efficiently handles duplicate phrases and ensures that the final results are lexicographically ordered.

Code Solutions

def before_after_puzzles(phrases):
    # Precompute the first and last words for each phrase.
    first_words = [phrase.split()[0] for phrase in phrases]
    last_words = [phrase.split()[-1] for phrase in phrases]
    
    # Use a set to store unique puzzles.
    results = set()
    
    # Iterate over every pair of phrases.
    for i in range(len(phrases)):
        for j in range(len(phrases)):
            if i == j:
                continue
            # Check if the last word of phrase[i] matches the first word of phrase[j].
            if last_words[i] == first_words[j]:
                # Merge phrases by appending phrase[j] without its first word.
                merged = phrases[i] + phrases[j][len(first_words[j]):]
                results.add(merged)
    
    # Return the puzzles sorted lexicographically.
    return sorted(results)

# Example usage:
if __name__ == '__main__':
    phrases = ["writing code", "code rocks"]
    print(before_after_puzzles(phrases))
← Back to All Questions