Glued Phrases

Medium

You are given a list of phrases. Each phrase is made of words in lowercase English letters separated by single spaces, with no leading or trailing spaces. Two phrases can be glued together when the last word of the first one equals the first word of the second: the shared word is written once, so "green tea" and "tea party" become "green tea party". Try every ordered pair of phrases with different indices i and j (order matters: gluing i to j and j to i are separate options) and return all distinct glued phrases sorted lexicographically.

Example 1

phrases=['green tea', 'tea party', 'party time', 'big green'] → ['big green tea', 'green tea party', 'tea party time']

"green tea" ends with tea and "tea party" starts with it, giving "green tea party". In the same way "tea party" + "party time" and "big green" + "green tea" are glued.

Example 2

phrases=['go', 'go', 'stop'] → ['go']

The two separate "go" phrases glue into "go" (the shared word is written once) in both orders, but the answer lists it only once.

Example 3

phrases=['sun rises', 'moon sets'] → []

No phrase starts with the last word of another, so the answer is empty.

Constraints

1 ≤ len(phrases) ≤ 100
1 ≤ len(phrases[i]) ≤ 100
phrases[i] consists of lowercase English letters and single spaces, with no spaces at either end

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Hash Table String Sorting

Similar problems

Anagram Buckets Medium A Subsequence of One Word Only Medium Most Searched Words Medium Word Grown Letter by Letter Medium Merge Contact Cards Medium

Input

phrases=['green tea', 'tea party', 'party time', 'big green']

Expected

['big green tea', 'green tea party', 'tea party time']

Run checks the first 3 tests in your browser. Submit checks all 68 tests on the server, hidden ones included.