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 "".

Example 1: Input: strs = ["flower","flow","flight"] Output: "fl"

Example 2: Input: strs = ["dog","racecar","car"] Output: "" Explanation: There is no common prefix among the input strings.

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 "dog", "racecar", and "car".

Example 3

Input

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

Output

"apple"

Explanation. All strings are identical, so the entire string "apple" is the common prefix.

Example 4

Input

[
  "[\"apple\",\"apricot\",\"apply\"]"
]

Output

"ap"

Explanation. The longest common prefix among "apple", "apricot", and "apply" is "ap".

Example 5

Input

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

Output

Explanation. If one of the strings is empty, the common prefix must be empty.

Example 6

Input

[
  "[\"a\"]"
]

Output

"a"

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

Example 7

Input

[
  "[\"aa\",\"a\"]"
]

Output

"a"

Explanation. The shorter string 'a' is a prefix of 'aa'.

Follow-up: Can you optimize your solution to handle cases where the input array `strs` is extremely large but the strings themselves are relatively short? Consider a Trie-based approach or a divide and conquer strategy.

Constraints:

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

Views: 2