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 "".All given inputs are in lowercase English letters a-z.

Constraints

  • 0 <= strs.length <= 200
  • 0 <= strs[i].length <= 200
  • strs[i] consists of only lowercase English letters.

Example

Input: strs = ["flower","flow","flight"]
Output: "fl"

Solution

Approach: Horizontal Scanning

  1. Initialize the prefix with the first string in the array.
  2. Iterate through the rest of the strings in the array, starting from the second string.
  3. For each string, check if the current prefix is a prefix of the string.
    • If it's not, shorten the prefix by one character from the end until it becomes a prefix of the current string.
    • If prefix becomes an empty string at any point, it means there is no common prefix among all strings, so return "" immediately.
  4. After iterating through all strings, the remaining prefix will be the longest common prefix.

Python Implementation

class Solution:
    def longestCommonPrefix(self, strs: list[str]) -> str:
        if not strs:
            return ""

        prefix = strs[0]
        for i in range(1, len(strs)):
            current_string = strs[i]
            while not current_string.startswith(prefix):
                prefix = prefix[:-1] # Shorten prefix by one character
                if not prefix:
                    return ""
        return prefix