Longest Common Prefix [Solution]

Solution 1: Sort It First

Below is a Python implementation of the longest_common_prefix function to find the longest common prefix among an array of strings:

from typing import List

def longest_common_prefix(strs: List[str]) -> str:
    """
    Find the longest common prefix among an array of strings.

    Parameters:
    - strs: List of strings.

    Returns:
    - str: Longest common prefix or an empty string if none.
    """
    if not strs:
        return ""

    # Sort the strings to easily compare the first and last strings
    strs.sort()

    # Compare the first and last strings to find the common prefix
    common_prefix = ""
    for i in range(len(strs[0])):
        if strs[0][i] == strs[-1][i]:
            common_prefix += strs[0][i]
        else:
            break

    return common_prefix

# Example usage:
strs = ["bake", "bam", "bats"]
result = longest_common_prefix(strs)
print(result)  # Output: "ba"

strs = ["i", "write", "iwrite"]
result = longest_common_prefix(strs)
print(result)  # Output: ""

strs = ["", "one"]
result = longest_common_prefix(strs)
print(result)  # Output: ""

strs = ["two", "two", "two"]
result = longest_common_prefix(strs)
print(result)  # Output: "two"

Time Complexity:

Let’s break down the time complexity analysis for the longest_common_prefix function:

1. Sorting Step:

   strs.sort()
   

   The sorting step takes O(n * log(n)) time, where n is the number of strings in the array. Sorting is a logarithmic time operation, and in this case, we are sorting the list of strings.

2. Common Prefix Identification:

   for i in range(len(strs[0])):
   

   In the worst case, the loop iterates through the entire length of the common prefix in the first string. Let’s denote the length of the common prefix as m.

   • In each iteration, we perform constant-time operations (comparisons).
   • The loop runs for a maximum of m iterations. Therefore, the common prefix identification step takes O(m) time.
3. Overall Time Complexity:
   • The overall time complexity, considering both the sorting step and the common prefix identification step, is O(m + n * log(n)).
   • Specifically, if the length of the common prefix (or the length of the first string after sorting) significantly surpasses the number of strings, the time complexity tends to be closer to O(m).
   • Conversely, if the number of strings greatly exceeds the length of the common prefix, the time complexity tends to be closer to O(n * log(n)).

Space Complexity:

The space complexity is O(m), where m is the length of the common prefix.

Solution 2: Without Sorting

from typing import List

def longest_common_prefix(strs: List[str]) -> str:
    """
    Find the longest common prefix among an array of strings.

    Parameters:
    - strs: List of strings.

    Returns:
    - str: Longest common prefix or an empty string if none.
    """
    if not strs:
        return ""

    # Find the minimum length among all strings
    min_length = min(len(s) for s in strs)

    common_prefix = ""
    for i in range(min_length):
        # Check if the characters at the current position are the same for all strings
        if all(s[i] == strs[0][i] for s in strs):
            common_prefix += strs[0][i]
        else:
            break

    return common_prefix

# Example usage:
strs = ["bake", "bam", "bats"]
result = longest_common_prefix(strs)
print(result)  # Output: "ba"

strs = ["i", "write", "iwrite"]
result = longest_common_prefix(strs)
print(result)  # Output: ""

strs = ["", "one"]
result = longest_common_prefix(strs)
print(result)  # Output: ""

strs = ["two", "two", "two"]
result = longest_common_prefix(strs)
print(result)  # Output: "two"

In this solution, we find the minimum length among all strings and iterate only up to that length. We then check if the characters at the current position are the same for all strings, and if so, append that character to the common prefix.

Time Complexity:

This approach ensures linear time complexity of O(m * n), where m is the length of the common prefix and n is the number of strings in the array.

Space Complexity:

The space complexity is O(m), where m is the length of the common prefix.