Python Programming Challenge 17: Longest Common Prefix

In today’s post, we’ll discuss the Leetcode 14 problem – finding the longest common prefix amongst a list of strings.

Leetcode Longest Common Prefix Problem

For this challenge, you are required to write a function called longestCommonPrefix() that accepts a list of strings called strs.

The function needs to return the longest prefix that is common amongst all the strings in the list. For instance, suppose strs is ['Grape', 'Group', 'Ground', 'Grind'], the function should return the string 'Gr'.

If the strings in the input list do not have any common prefix, the function should return the empty string. For instance, if strs is ['Hello', 'Joy', 'Mellow'], the function should return ''.

Here are more examples of how the function should work:

Example 1

# Input
strs = ['Joy', 'Roy', 'Toy']
# Return value
''

Example 2

# Input
strs = ['Happy', 'Happen', 'Happiness']
# Return value
'Happ'

Example 3

# Input
strs = ['Happy', 'Happen', 'Merry']
# Return value
''

Example 4

# Input
strs = []
# Return value
''

Example 5

# Input
strs = ['Today']
# Return value
'Today'

Suggested Approach

The longest common prefix problem is relatively easy to solve.

The easiest way is to find the length of the shortest string in strs. Suppose this length is m. We’ll compare the first m letters of each of the strings in strs to determine if the letters are the same.

For instance, suppose strs is ['Hello', 'Help', 'Hem'].

We first determine the length of the shortest string to be 3 ('Hem').

Next, we use a loop to check the first 3 letters of each string in strs one by one.

We start with the first letter. If the first letter in any of the strings is different from the first letter in the first string ('Hello'), we return an empty string.

Else, we move on to the second letter.

If the second letter in any of the strings is different from the second letter in 'Hello', we return 'H'.

Else, we move on to the third letter.

If the third letter in any of the strings is different from the third letter in 'Hello', we return 'He'.

In our example above, the third letter in 'Hem' is different from the third letter in 'Hello'. Hence, we return 'He' as the result.

Based on the description above, try completing this challenge yourself.

Suggested Solution

The suggested solution for the Longest Common Prefix problem is given below:

def longestCommonPrefix(strs):
    if len(strs) == 0:
        return ''
    elif len(strs) == 1:
        return strs[0]

    m = len(min(strs, key=len))
    i = 0
    reference = strs[0]

    while i < m:        
        for myStr in strs:
            if myStr[i] != reference[i]:
                return reference[:i]
        i += 1

    return reference[:m]

Here, we first define a function called longestCommonPrefix() that has one parameter – strs.

Two Special Cases

Next, we use an if-else statement to deal with two special cases where there is no need to iterate through strs. These two cases correspond to examples 4 and 5 in the first section above. If strs is an empty string, the longest common prefix is an empty string. Hence, we return '' on line 3.

On the other hand, if strs only has one element, we return that element (on line 5).

Finding Length of Shortest String in Input List

Next, we use the built-in min() function to find the string with the shortest length on line 7. We do that by passing the argument key=len to the min() function. If you are unfamiliar with the key=len argument, you should check out this post where we discuss the max() function and how the key=len argument works.

The min() function returns the string with the shortest length. We pass this string to the len() function to get the length and assign the result to a variable called m (on line 7).

Next, we declare a variable i and initialize it to 0.

On line 9, we assign the first string in strs to a variable called reference. As the name suggests, we’ll be using this string as a reference later.

Comparing First m Letters, For Each String in strs

From lines 11 to 15, we have a while loop that runs m times (from i equals 0 to i equals m - 1).

Inside the loop, we use a for loop to iterate through the strings in strs. For each string in strs, we compare each letter in that string (denoted by myStr) with the corresponding letter in reference (on line 13). Once we find a letter that is different, we know that the prefix is no longer common.

Hence, we use the slice [:i] to return the first i letters in reference (on line 14).

For instance, when i equals 2, we are comparing the 3^rd letter in myStr with the 3^rd letter in reference. If the 3^rd letter is different, we use the slice [:2] to return the first two letters in reference.

After Comparing The First m Letters

After completing the while loop, if we do not find any letter that is different in the first m letters, we return the string reference[:m]  (which contains the first m letters in reference) on line 17.

We only return the first m letters in reference as the longest common prefix cannot be longer than the shortest string in strs. For instance, if strs is ['Hello', 'Help', 'He'], the length of the shortest string is 2. Hence, the length of the longest common prefix cannot be longer than 2.

Since the first two letters in all the three strings in strs are the same, the return statement on line 14 (inside the while loop) will not be executed.

Instead, we’ll reach the return statement on line 17. This statement returns the string reference[:2] (i.e. it returns the string 'He'), which is what we want.

With that, the function is complete.