14. Longest Common Prefix

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.

    def longestCommonPrefix(self, strs: List[str]) -> str:

        if not strs:
            return ""

        # Sort the strings to bring the potential common prefix to the beginning
        strs.sort()
        
        # Consider the first and last strings after sorting
        first_str = strs[0]
        last_str = strs[-1]
        
        # Find the common prefix between the first and last strings
        common_prefix = []

        for i in range(len(first_str)):
            if i < len(last_str) and first_str[i] == last_str[i]:
                common_prefix.append(first_str[i])
            else:
                break

        return "".join(common_prefix)