Longest Common Prefix (via Leetcode)¶

Date published: 2020-03-25

Category: Python

Subcategory: Beginner Algorithms

Tags: functions, loops, try-except statement

This problem can be found on Leetcode.

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

Test Cases¶

In this test case, the longest common prefix of characters among the three strings is "fl"

In [51]:

# assert longest_common_prefix(["flower", "flow", "flight"]) == "fl"

# assert longest_common_prefix(["flower", "flow", "flight"]) == "fl"

In this test case, there are no common prefix characters among the three strings so the function should return an empty string.

In [52]:

# assert longest_common_prefix(["dog", "racecar", "car"]) == ""

# assert longest_common_prefix(["dog", "racecar", "car"]) == ""

Pseudocode¶

In [54]:

# create a function that takes in a list of strings

    # letter_at_index = ""  # stores our running letter to compare to each word
    # final_string = ""  # hold longest common prefix that will be the return value

    # this condition is here because the code to calculate the length of the first item in the input list of strings would cause an error...
    # if length of the input list of strings is 0:
        # there are no strings to evaluate so immediately return final_string
    
    # assign variable to be length of one of the input strings

    # iterate from letter_index of range 0 to one of the length of the input strings:
        # iterate over each string in list and keep track of index too
            
            # add try block b/c we'd want our function to end when we reach an index error in the except statement below
                # if we're iterating over first list item
                    # letter_at_index = this letter in first list item
                # else if letter_at_index is not equal to the letter in this list item:
                    # use the last saved common prefix among strings
                    # return final_string
                # else:  
                    # pass
            # except index error:
                # at this point we may be trying to access a character in a strong beyond its max index...
                # break out of function and return final_string
                
        # finished iteration of comparing same index among strings...
        # letter_at_index exists in all strings so append it to final string 
        # assign letter_at_index to a blank string

    # we've finished iteration and all strings are the same!
    # return final_string

# create a function that takes in a list of strings # letter_at_index = "" # stores our running letter to compare to each word # final_string = "" # hold longest common prefix that will be the return value # this condition is here because the code to calculate the length of the first item in the input list of strings would cause an error... # if length of the input list of strings is 0: # there are no strings to evaluate so immediately return final_string # assign variable to be length of one of the input strings # iterate from letter_index of range 0 to one of the length of the input strings: # iterate over each string in list and keep track of index too # add try block b/c we'd want our function to end when we reach an index error in the except statement below # if we're iterating over first list item # letter_at_index = this letter in first list item # else if letter_at_index is not equal to the letter in this list item: # use the last saved common prefix among strings # return final_string # else: # pass # except index error: # at this point we may be trying to access a character in a strong beyond its max index... # break out of function and return final_string # finished iteration of comparing same index among strings... # letter_at_index exists in all strings so append it to final string # assign letter_at_index to a blank string # we've finished iteration and all strings are the same! # return final_string

I want to cover the space and time complexity here.

n is the length of elements in list_of_strings. m is the length of the longest string in list_of_strings.

My iteration could be over all possible letters in each string so it's an O(mn) time complexity operation.

There are a few variables created that are each an O(1) space complexity operation. Since they're all very small, space complexity is essentially O(1).

Code¶

In [93]:

def longest_common_prefix(list_of_strings):
    letter_at_index = ""
    final_string = ""
    
    if len(list_of_strings) == 0:
        return final_string
    
    length_of_a_string = len(list_of_strings[0])
    
    # compare the letter at an index for each string and see if they match...
    for index_in_string in range(0, length_of_a_string):
        for index_in_list_of_strings, string in enumerate(list_of_strings):
            try:    
                if index_in_list_of_strings == 0:
                    letter_at_index = string[index_in_string]
                elif string[index_in_string] != letter_at_index:
                    return final_string
                else:
                    pass
            except IndexError:
                return final_string
        # letter_at_index is the same across all strings so add this letter to final_string
        final_string += letter_at_index
        # reassign letter_at_index to be an empty string
        letter_at_index = ""
    
    return final_string

def longest_common_prefix(list_of_strings): letter_at_index = "" final_string = "" if len(list_of_strings) == 0: return final_string length_of_a_string = len(list_of_strings[0]) # compare the letter at an index for each string and see if they match... for index_in_string in range(0, length_of_a_string): for index_in_list_of_strings, string in enumerate(list_of_strings): try: if index_in_list_of_strings == 0: letter_at_index = string[index_in_string] elif string[index_in_string] != letter_at_index: return final_string else: pass except IndexError: return final_string # letter_at_index is the same across all strings so add this letter to final_string final_string += letter_at_index # reassign letter_at_index to be an empty string letter_at_index = "" return final_string

Validate Code with Test Cases¶

In [94]:

assert longest_common_prefix(["flower", "flow", "flight"]) == "fl"

assert longest_common_prefix(["flower", "flow", "flight"]) == "fl"

In [95]:

assert longest_common_prefix(["flower", "flower", "flower"]) == "flower"

assert longest_common_prefix(["flower", "flower", "flower"]) == "flower"

In [96]:

assert longest_common_prefix(["", "racecar", "car"]) == ""

assert longest_common_prefix(["", "racecar", "car"]) == ""

In [97]:

assert longest_common_prefix(["", "", ""]) == ""

assert longest_common_prefix(["", "", ""]) == ""

In [98]:

assert longest_common_prefix([""]) == ""

assert longest_common_prefix([""]) == ""

In [100]:

assert longest_common_prefix([]) == ""

assert longest_common_prefix([]) == ""