Before And After Puzzle - Leetcode Solution

Before And After Puzzle is a problem on leetcode that asks us to find all possible phrases that can be formed by concatenating the last word of one phrase with the first word of another phrase. Here is the detailed solution to this problem:

1. First, we need to split each phrase into individual words. This can be done easily using the split() method in Python. We will create a list of lists to store these words. Each sublist will represent a phrase.

2. Next, we need to create a dictionary that maps the first word of each phrase to its index in the list of phrases. We will process each phrase and create a mapping for its first word if it doesn't already exist in the dictionary.

3. After creating the dictionary, we will iterate through each phrase and find all the possible matches by looking up the last word of the phrase in the dictionary. If a match is found, we will append the combined phrase to a list of results.

4. Finally, we will sort and return the list of results.

Here is the Python code to implement this solution:

class Solution:
    def beforeAndAfterPuzzles(self, phrases: List[str]) -> List[str]:
        # Split each phrase into individual words
        phrase_words = [phrase.split() for phrase in phrases]
        n = len(phrase_words)
        # Create a dictionary that maps the first word of each phrase to its index
        first_word_map = {}
        for i in range(n):
            first_word = phrase_words[i][0]
            if first_word not in first_word_map:
                first_word_map[first_word] = []
            first_word_map[first_word].append(i)
        # Find all possible matches
        results = set()
        for i in range(n):
            last_word = phrase_words[i][-1]
            if last_word in first_word_map:
                for j in first_word_map[last_word]:
                    if i != j:
                        results.add(' '.join(phrase_words[i] + phrase_words[j][1:]))
        # Sort and return the list of results
        return sorted(results)

Time Complexity: O(n * m), where n is the number of phrases and m is the average number of words in each phrase. The loop that creates the dictionary and the loop that finds all possible matches run in O(n) and O(m) time respectively.

Space Complexity: O(n + m), the space required to create the list of phrase words and the dictionary.

1