How hard is LeetCode 1181. Before and After Puzzle?

LeetCode 1181. Before and After Puzzle is rated Medium on LeetCode.

What is the time complexity of LeetCode 1181. Before and After Puzzle?

The Python solution on this page runs in O(n^2 \times m \times (\log n + \log m)).

What is the space complexity of LeetCode 1181. Before and After Puzzle?

The Python solution on this page uses O(n^2 \times m) auxiliary space.

What topics does LeetCode 1181. Before and After Puzzle cover?

LeetCode 1181. Before and After Puzzle is tagged Array, Hash Table, String and Sorting on LeetCode.

Is LeetCode 1181. Before and After Puzzle a premium problem?

Yes. LeetCode 1181. Before and After Puzzle is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.

Before and After Puzzle — LeetCode 1181 Python Solution

MediumLeetCode PremiumArrayHash TableStringSorting

Problem: #1181
Pattern: Sorting
Reading time: 2 min
Source: leetcode.com

The problem

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.

Python solution

Python

class Solution:
    def beforeAndAfterPuzzles(self, phrases: List[str]) -> List[str]:
        ps = []
        for p in phrases:
            ws = p.split()
            ps.append((ws[0], ws[-1]))
        n = len(ps)
        ans = []
        for i in range(n):
            for j in range(n):
                if i != j and ps[i][1] == ps[j][0]:
                    ans.append(phrases[i] + phrases[j][len(ps[j][0]) :])
        return sorted(set(ans))

Complexity

Measure	Complexity
Time	O(n^2 \times m \times (\log n + \log m))
Space	O(n^2 \times m) auxiliary

Pattern: Sorting

Spend O(n log n) once to buy an ordering that makes the rest of the problem trivial. LeetCode 1181. Before and After Puzzle is filed here because LeetCode tags it Sorting, which is the vocabulary this hub collects.

The sorting guide has the Python template for the pattern and the 401 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 1181. Before and After Puzzle?: LeetCode 1181. Before and After Puzzle is rated Medium on LeetCode.
What is the time complexity of LeetCode 1181. Before and After Puzzle?: The Python solution on this page runs in O(n^2 \times m \times (\log n + \log m)).
What is the space complexity of LeetCode 1181. Before and After Puzzle?: The Python solution on this page uses O(n^2 \times m) auxiliary space.
What topics does LeetCode 1181. Before and After Puzzle cover?: LeetCode 1181. Before and After Puzzle is tagged Array, Hash Table, String and Sorting on LeetCode.
Is LeetCode 1181. Before and After Puzzle a premium problem?: Yes. LeetCode 1181. Before and After Puzzle is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.