Longest Common Prefix

March 30, 2020

I’m trying to get in a habit of starting my mornings off with coffee and a Leetcode problem before work. Ease my way into the day and get the brain juices flowing. Let’s jump in!

Longest Common Prefix


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

All given inputs are in lowercase letters a-z.

Example inputs:

Input: ["flower","flow","flight"]
Output: "fl"

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


This one seems pretty straight forward.

Maintain an index and loop through each string, checking the current character to see if it is the same. If it’s not, or we run out of characters in one of the strings, we’re done.

With that index, just slice the string to get the prefix.

Corner Cases

The following corner cases are what I missed in my initial solution:


Inlining the is_equal_at_index function inside of the loop will likely increase runtime speed here at the cost of readability.


class Solution:
    def is_equal_at_index(self, strs: List[str], i: int) -> bool:
        char = strs[0][i]
        for j in range(1, len(strs)):
            if char != strs[j][i]:
                return False
        return True

    def longestCommonPrefix(self, strs: List[str]) -> str:
        i = 0

        while True:
                if not self.is_equal_at_index(strs, i):
            except IndexError:
                i += 1

        return strs[0][0:i] if i > 0 else ''


Runtime: 32 ms, faster than 66.42% of Python3 online submissions for Longest Common Prefix.
Memory Usage: 13.9 MB, less than 6.67% of Python3 online submissions for Longest Common Prefix.

Return home