Longest Common Prefix

Given a list of strings, find the longest string that is a prefix of every one of them. Return an empty string if there's no common prefix.

Example

Input: flower flow flight Output: fl

Approach

You don't need to build a full trie for this one — a simpler "shrink a candidate" approach works: start with the first word as your candidate prefix, then for every other word, keep chopping one character off the end of the candidate until that word actually starts with it. If the candidate ever becomes empty, there's no common prefix at all.

Input format

Line 1: the words, space-separated

Print the longest common prefix (an empty line if there is none).