Coder's Cat

2019-12-03

## Leetcode Question

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 “”.

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.

The performance result is:

### Optimize with sorting

If we sort the array of strings in alphabetically, we only need to find the common prefix of first and last string.

Think about a testcase:

ab abc ax
common prefix is: common_prefix(“ab”, “ax”) => “a”

The time performance gets much better: