Longest Common Prefix

Problem

Let’s take a look at the 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 "".

Click on the above card to go to the problem on LeetCode.

Approach

No way this is an easy question.

We’re going to follow a slightly different approach.

Handle all the edge cases

pretty important imo

Initialize prefix

Just use the first string it the array as the prefix

iterate over the rest of the strings

Now, iterate over the elements except the first one (we’re using that as the prefix).

Use a while loop.

We’re just going to trim the following strings up to the length of the prefix and compare it with the prefix itself.

If it does not match, we are going to trim the prefix by one and compare again.

this process goes on until the prefix is matched (then we are moved to the next string in the list) or the prefix becomes an empty string (then we are returning an empty string).

Solution

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:

        if not strs: return ""
        if len(strs) == 1: return strs[0]
        prefix = strs[0]

        for s in strs[1:]:
            while s[:len(prefix)] != prefix:
                prefix = prefix[:-1]
                if not prefix: return ""
            
        
        return prefix