Every Start Is a Word

Medium

You are given a list of words words. Call a word *complete* if every non-empty prefix of it (the word itself included) also appears in words. For example, with words = ['b', 'bo', 'box'] the word box is complete: b, bo and box are all in the list. Return the longest complete word. If several complete words share that length, return the alphabetically smallest one. If there are no complete words, return the empty string.

Example 1

words=['t', 'te', 'tea', 'team', 'teal', 'ten'] → 'teal'

Both team and teal have all their prefixes (t, te, tea) in the list. Both have length 4, and teal is alphabetically smaller.

Example 2

words=['dog', 'do', 'cat'] → ''

There are no one-letter words, so no word qualifies.

Example 3

words=['q', 'qu', 'quiz', 'x'] → 'qu'

quiz is missing its prefix qui, so the best answer is qu.

Constraints

1 ≤ len(words) ≤ 10⁵
1 ≤ len(words[i])
The total length of all words is at most 10⁵
Words consist of lowercase English letters only

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Depth-First Search Trie

Similar problems

Numbers in Dictionary Order Medium Outermost Folders Only Medium Words Built From Shorter Words Hard Best XOR Up the Chain of Command Hard XOR of Two Disjoint Subtrees Hard

Input

words=['t', 'te', 'tea', 'team', 'teal', 'ten']

Expected

'teal'

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