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.

    Leave a Reply

    Your email address will not be published. Required fields are marked *