Longest Common Prefix

mediumSave

ArrayString

Write a function longestCommonPrefix(strs) that takes an array of strings strs as input. The function should return the longest common prefix string amongst all strings in the array. If there is no common prefix, return an empty string "".

Examples

Example 1: Input: strs = ["flower","flow","flight"] Output: "fl" Explanation: The longest common prefix among "flower", "flow", and "flight" is "fl".

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

Example 3: Input: strs = ["apple","apricot","apply"] Output: "ap" Explanation: The longest common prefix is "ap".

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\"]"
]

Output

"apple"

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

Example 4

Input

[
  "[]"
]

Output

Explanation. An empty array of strings has no common prefix.

Example 5

Input

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

Output

Explanation. If any string is empty, or if the first string is empty, there can be no common prefix longer than an empty string.

Example 6

Input

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

Output

"apple"

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

Example 7

Input

[
  "[\"programming\",\"program\",\"pro\"]"
]

Output

"pro"

Explanation. The longest common prefix for 'programming', 'program', and 'pro' is 'pro'.

Example 8

Input

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

Output

"abcde"

Explanation. The common prefix gradually shortens based on the shortest common segment.

Example 9

Input

[
  "[\"a\"]"
]

Output

"a"

Explanation. Single character string is its own prefix.

Example 10

Input

[
  "[\"abc\",\"abd\",\"abe\"]"
]

Output

"ab"

Explanation. Strings differ at the third character, so 'ab' is the common prefix.

Follow-up: Can you solve this problem with a divide and conquer approach, or using a Trie data structure, to potentially improve performance for very large inputs, especially when the number of strings or string lengths are significantly large?

Constraints:

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

Views: 3