Problem statement

https://leetcode.com/problems/before-and-after-puzzle/

Solution

What we need to do is for each sentence extract first and last word and create hash tables starts: which for each word say which phrases start with it and ends: similar for end. Then for each starting word we check if we have ending word and add all pairs to our answer.

Complexity

Time complexity is O(n*k) to put all phrases in dictionary, where k is average length of phrase. Then we need to create answer and potentially we can have O(n^2) good candidates each of them can have size O(k). So, overall time complexity is O(n^2 k), space complexity as well.

Code

class Solution:
    def beforeAndAfterPuzzles(self, phrases):
        phrases, ans = [p.split() for p in phrases], []
        starts, ends = defaultdict(list), defaultdict(list)

        for i, p in enumerate(phrases):
            starts[p[0]].append(i)
            ends[p[-1]].append(i)

        for s in starts:
            if s in ends:
                for x, y in product(starts[s], ends[s]):
                    if x == y: continue
                    ans.append(" ".join(phrases[y][:-1] + phrases[x]))

        return sorted(set(ans))