Write a Python function to find the longest common prefix among a list of strings.
JackBrn
Posted by JackBrn
Last Updated: August 19, 2024
Python Strings
Finding the Longest Common Prefix in Python
Determining the longest common prefix among a list of strings is a common problem in computational tasks. A prefix is defined as any leading segment of a string. Below, you will find a Python function that efficiently calculates the longest common prefix for a given list of strings.
Function Implementation
def longest_common_prefix(strs):
    if not strs:
        return ""
    
    # Start with the first string as the potential prefix
    prefix = strs[0]
    
    for string in strs[1:]:
        # Reduce the prefix until it matches the start of the string
        while string[:len(prefix)] != prefix and prefix:
            prefix = prefix[:-1]  # Remove the last character
            
    return prefix
How It Works
1. Check for Empty List: The function first checks if the input list strs is empty. If it is, the function returns an empty string. 2. Initialize Prefix: The first string in the list is chosen as the initial prefix. 3. Iterate Over Strings: For each subsequent string in the list, the function checks whether the current prefix is a prefix of that string. 4. Reduce Prefix: If the prefix does not match the beginning of the string, the last character of the prefix is removed and the check is repeated until a match is found or the prefix becomes empty. 5. Return Result: Finally, the longest common prefix found is returned.
Example Usage
The function can be tested with various examples: 
# Example 1
strings = ["flower", "flow", "flight"]
print(longest_common_prefix(strings))  # Output: "fl"

# Example 2
strings = ["dog", "racecar", "car"]
print(longest_common_prefix(strings))  # Output: ""

# Example 3
strings = ["interview", "international", "internet"]
print(longest_common_prefix(strings))  # Output: "inter"
Complexity Analysis
- Time Complexity: The worst-case scenario occurs when all strings are identical, leading to a complexity of O(n * m), where n is the number of strings and m is the length of the common prefix. - Space Complexity: O(1) additional space, as the operation is performed in place. This function provides a straightforward approach to finding the longest common prefix in a collection of strings, making it both efficient and easy to understand.
Default Image