14. Longest Common Prefix

Problem Statement in English

You’re given an array of strings strs. Write a function to find the longest common prefix string amongst an array of strings.

Return an empty string "" if there is no common prefix.

Approach

We can solve this using either nested loops or sorting. The nested loop approach would take $O(n \cdot m)$ time, where $n$ is the number of strings and $m$ is the length of the longest string.

In the sorting approach, we sort the array of strings and then compare the first and last strings. The longest common prefix will be the same for both the first and last strings after sorting.

Since we sort the string we don’t need to check all the strings, we only need to check the first and last strings. This is because if there is a common prefix, it will be present in both the first and last strings after sorting.

And we’re done!

Solution in Python

class Solution:
    def longestCommonPrefix(self, v: List[str]) -> str:
        ans = ""
        v = sorted(v)
        first = v[0]
        last = v[-1]
        for i in range(min(len(first), len(last))):
            if first[i] != last[i]:
                return ans
            ans += first[i]
        return ans

Complexity

• Time: $O(m \cdot n \cdot log(n))$
  where $m$ is the length of the longest string in the list and $n$ is the number of strings in the list. The sorting step takes $O(n \cdot log(n))$ time, and comparing the first and last strings takes $O(m)$ time.

• Space: $O(1)$
  Since we are not using any extra space, the space complexity is $O(1)$.

Mistakes I Made

I used a nested loop 😝

And we are done.