# 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

### Problem

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.
``````

### Thinking

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:

• Handling the zero/empty string case.

### Improvements

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

### Solution

``````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:
try:
if not self.is_equal_at_index(strs, i):
break
except IndexError:
break
else:
i += 1

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

``````

### Score

``````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