Longest Common Prefix easy

Problem Statement

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.

Steps:

1. Handle Empty Input: Check if the input list strs is empty or contains an empty string. If so, return an empty string "" as there's no common prefix.

2. Initialize Prefix: Start with the first string in the list as the initial common prefix.

3. Iterate and Compare: Iterate through the remaining strings in the list. For each string:

   • Compare the current prefix with the current string character by character.
   • If a mismatch is found, shorten the prefix to the characters before the mismatch.
   • If the current string is shorter than the prefix, shorten the prefix to the length of the current string.

4. Return Prefix: After iterating through all strings, the remaining prefix is the longest common prefix.

Explanation:

The algorithm uses a character-by-character comparison approach. It starts by assuming the first string is the common prefix. Then, it iterates through the rest of the strings, comparing characters one by one against the current prefix. Whenever a mismatch occurs, it truncates the prefix to the point of the mismatch. This ensures that the prefix remains common to all strings encountered so far. The process continues until all strings have been checked, at which point the final prefix is the longest common prefix.

Code:

def longestCommonPrefix(strs):
    """
    Finds the longest common prefix string amongst an array of strings.

    Args:
      strs: A list of strings.

    Returns:
      The longest common prefix string, or "" if there is none.
    """

    if not strs or "" in strs:  # Handle empty input or empty strings
        return ""

    prefix = strs[0]  # Initialize prefix with the first string

    for i in range(1, len(strs)):
        j = 0
        while j < len(prefix) and j < len(strs[i]) and prefix[j] == strs[i][j]:
            j += 1
        prefix = prefix[:j]  # Shorten the prefix if a mismatch is found

    return prefix

Complexity:

• Time Complexity: O(S), where S is the sum of the lengths of all strings in the input list. In the worst case, we might need to compare all characters of all strings.
• Space Complexity: O(1). The algorithm uses a constant amount of extra space regardless of the input size. The prefix variable is at most the length of the shortest string.