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 "".

Function Signature:

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.
    """
    # Your code here

Example:


# Input: strs = ["bake", "bam", "bats"]
# Output: "ba"

# Input: strs = ["i", "write", "iwrite"]
# Output: ""
# Explanation: There is no common prefix among the strings.

# Input: strs = ["", "one"]
# Output: ""
# Explanation: There is no common prefix among the strings.

# Input: strs = ["two", "two", "two"]
# Output: "two"

Note:

  • All given inputs are in lowercase letters a-z.

Instructions:

  • Write the longest_common_prefix function to solve the problem.
  • Implement your solution in Python.
  • Provide clear comments in your code.
  • Discuss the time and space complexity of your solution.

As always, we’ll share our solution to this problem tomorrow. Stay tuned 😊