Leetcode 14: Longest Common Prefix on given list of strings

As part of the programming series, we will review the longest common prefix question which is categorized as an easy problem in Leetcode. In this exercise, we will use Python 3 to write the code.

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

• Example 1:
  • Input: strs = [“flower”,”flow”,”flight”]
  • Output: “fl”

• Example 2:
  • Input: strs = [“dog”,”racecar”,”car”]
  • Output: “”
  • Explanation: There is no common prefix among the input strings.

• Constraints:
  • 1 <= strs.length <= 200
  • 0 <= strs[i].length <= 200
  • strs[i] consists of only lowercase English letters.

Algorithm

The algorithm works by initializing the prefix as the first string in the input list. Then, it iterates through the remaining strings in the list and compares the prefix with each string. If the prefix is not a prefix of the current string, it removes the last character from the prefix and continues the comparison. This process continues until the prefix is a prefix of all the strings or until the prefix becomes an empty string.

Time complexity

• Let n be the length of the longest string in the input list and m be the number of strings in the list.
• The algorithm iterates through the list of strings once, comparing the prefix with each string.
• In the worst case, the algorithm needs to compare the prefix with all the characters in each string.
• Therefore, the time complexity is O(n * m), where n is the length of the longest string and m is the number of strings.

Space complexity

• The algorithm uses a variable to store the prefix.
• The space complexity is O(n), where n is the length of the longest string in the input list.

Code

class Solution:
    def longestCommonPrefix(self, strs: list[str]) -> str:
        # Edge case: if the list is empty, return an empty string
        if not strs:
            return ""

        # Constraint: If the list has more than 200 strings, then return nothing
        if len(strs) > 200:
            return ""
        
        # Initialize the prefix
        prefix = strs[0]
        # Constraint: If string length is greater than 200 chars, then return nothing
        if len(strs[0]) > 200:
            return ""
        
        # Iterate through the list of strings
        for i in range(1, len(strs)):
            # Each string length cannot exceed 200 chars
            if len(strs[i]) > 200:
                return ""
            # Compare the prefix with the current string
            while strs[i].find(prefix) != 0:
                # We remove one character at the end until we find good match 
                prefix = prefix[:-1]
                # If we didn't find any match, return empty
                if not prefix:
                    return ""
        
        return prefix
    
if __name__ == "__main__":
    strs = ["flower","flow","flight"]
    solution = Solution()
    print(solution.longestCommonPrefix(strs))
    strs = ["dog","racecar","car"]
    print(solution.longestCommonPrefix(strs))

Output

Happy coding! Please add your comments.