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: ["flower","flow","flight"] Output: "fl" Example 2:
Input: ["dog","racecar","car"] Output: "" Explanation: There is no common prefix among the input strings.
Note: All given inputs are in lowercase letters a-z.
Explanation
Naive solution
It’s easy to find the common prefix of two string, the complexity is $O(M*N)$, where M and N is the length of two string.
For finding the common prefix of multiple strings, we start with the common prefix of the first two strings and iterate with the left strings. Just like finding the maximum of multiple values.
The complexity is $O(S * L)$, where S is the number of strings, and L is minimum length of strings.