Longest Common Prefix

mediumSave

ArrayStringString Matching

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

"fl"

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

"a"

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: 2