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

  • Input: strs is an array of strings.

  • Constraints:

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

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

Solution

The problem can be solved using horizontal scanning.

  • Initialization: Start by assuming the first string in the array is the prefix.
  • Iteration: Iterate through the rest of the strings in the array.
    • For each string s, continuously shorten the prefix from its end until s starts with prefix.
    • The str.find(prefix) method can be used to check if prefix is at the beginning of s (returns 0 if it is).
    • If at any point the prefix becomes an empty string, it means there is no common prefix among all strings, so return "" immediately.
  • Result: After checking all strings, the remaining prefix is the longest common prefix.
class Solution:
    def longestCommonPrefix(self, strs: list[str]) -> str:
        if not strs:
            return ""

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

        # Iterate through the rest of the strings
        for i in range(1, len(strs)):
            current_string = strs[i]
            # Shorten prefix until it's a prefix of current_string
            while current_string.find(prefix) != 0:
                prefix = prefix[:-1] # Remove last character
                if not prefix:
                    return "" # No common prefix found
        
        return prefix