All problems

Longest Common Prefix

Easy · string scan

Given a list of strings strs, return the longest string that every one of them starts with. This shared beginning is called the *common prefix*.

For example, "fl" is a prefix of "flower", "flow" and "flight", and no longer string is a prefix of all three. If the strings share no beginning at all, return the empty string "".

A string counts as a prefix of itself, and the empty string is a prefix of every string.

Examples

Example 1

Input: strs = ["flower", "flow", "flight"]

Output: "fl"

All three start with "fl", but the third letters (o, o, i) are not the same.

Example 2

Input: strs = ["dog", "racecar", "car"]

Output: ""

The first letters d, r and c all differ, so nothing is shared.

Example 3

Input: strs = ["apple"]

Output: "apple"

With a single string, the whole string is the common prefix.

Constraints

• 1 <= len(strs) <= 1000
• 0 <= len(strs[i]) <= 100
• strs[i] consists of lowercase English letters.