Solution for interview question: Longest Common Prefix

1. Understanding the Problem

Given an array of strings, find the longest common prefix among all strings.
If no common prefix exists, return an empty string "".

2. Handle Edge Cases

Before proceeding, handle cases where the input list is empty or contains only one string.
- If the list is empty, return an empty string.
- If the list has only one string, return that string as the common prefix.

from typing import List

def longest_common_prefix(strs: List[str]) -> str:
    if not strs:  # Empty list case
        return ""
    if len(strs) == 1:  # Single string case
        return strs[0]

3. Initialize the First String as a Reference Prefix

Start by assuming the entire first string in the array is the longest common prefix.
We’ll trim this prefix as we compare it to other strings in the array.

from typing import List

def longest_common_prefix(strs: List[str]) -> str:
    if not strs:
        return ""
    prefix = strs[0]  # Initialize with the first string as reference prefix
    return prefix

4. Iterate Over Each String and Adjust the Prefix

Loop through each string in the array (starting from the second string).
For each string, compare characters with the current prefix and shorten prefix if characters don’t match.

from typing import List

def longest_common_prefix(strs: List[str]) -> str:
    if not strs:
        return ""
    prefix = strs[0]
    for string in strs[1:]:
        # While prefix does not match the beginning of string, shorten it
        while not string.startswith(prefix):
            prefix = prefix[:-1]  # Remove the last character from prefix
            if not prefix:
                return ""  # No common prefix found
    return prefix

5. Return the Final Prefix

After iterating through all strings and adjusting the prefix, return the final value of prefix.
This value represents the longest common prefix shared by all strings in the array.

from typing import List

def longest_common_prefix(strs: List[str]) -> str:
    if not strs:
        return ""
    prefix = strs[0]
    for string in strs[1:]:
        while not string.startswith(prefix):
            prefix = prefix[:-1]
            if not prefix:
                return ""
    return prefix

6. Consider Edge Cases

Edge cases include:
- An array with an empty string, which results in an empty prefix.
- No common prefix across strings, which should return an empty string.
- All strings being identical, in which case the common prefix is the string itself.

from typing import List

def longest_common_prefix(strs: List[str]) -> str:
    if not strs:
        return ""
    prefix = strs[0]
    for string in strs[1:]:
        while not string.startswith(prefix):
            prefix = prefix[:-1]
            if not prefix:
                return ""  # Return empty if no common prefix
    return prefix