Longest Common Prefix

Medium

Write a function to find the longest common prefix string amongst an array of strings. If there is no common prefix, return an empty string "". All given inputs are lowercase English letters.

Example 1

Input

[
  "[\"flower\",\"flow\",\"flight\"]"
]

Output

Explanation. The longest common prefix among "flower", "flow", and "flight" is "fl".

Example 2

Input

[
  "[\"dog\",\"racecar\",\"car\"]"
]

Output

Explanation. There is no common prefix among the input strings.

Example 3

Input

[
  "[\"apple\"]"
]

Output

apple

Explanation. With only one string, the string itself is the longest common prefix.

Example 4

Input

[
  "[\"apple\",\"apple\",\"apple\"]"
]

Output

apple

Explanation. All strings are identical, so the string itself is the longest common prefix.

Example 5

Input

[
  "[\"\",\"b\"]"
]

Output

Explanation. One of the strings is empty, so no common prefix can exist.

Example 6

Input

[
  "[]"
]

Output

Explanation. The input array is empty, so there's no common prefix to find.

Example 7

Input

[
  "[\"ab\",\"a\"]"
]

Output

Explanation. The common prefix is 'a'.

Example 8

Input

[
  "[\"abcdefgh\",\"abcdef\",\"abcde\"]"
]

Output

abcde

Explanation. The longest common prefix is determined by the shortest string's common part.

Follow-up: Can you optimize your solution for cases where the input array `strs` is extremely large (e.g., millions of strings), or when the strings themselves are very long?

Constraints:

- 1 <= strs.length <= 200 - 0 <= strs[i].length <= 200 - strs[i] consists of only lowercase English letters.

Views: 8

Longest Common Prefix

Solution

Judge

Longest Common Prefix

Discussion (0)

Solution

Judge