14. Longest Common Prefix

Question

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 2

Input: strs = ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.

Solution 1: Sort By Len + String Compare

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        strs.sort(key=len)

        prefix = strs[0]
        # Compare for the rest of string
        for s in strs[1:]:
            if not s.startswith(prefix):
                for i in range(len(prefix)):
                    if prefix[i] != s[i]:
                        prefix = prefix[:i]
                        break
        return prefix

Time Complexity: O(N^2)
Space Complexity: O(1)

Solution 2: Sort By Alphabetic + String Compare

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if not strs:
            return strs
        
        strs.sort()
        n2 = min(len(strs[0]), len(strs[-1]))
        prefix = ''
        for i in range(n2):
            if strs[0][i] == strs[-1][i]:  
                prefix += strs[0][i]
            else:
                break
        return prefix

Time Complexity: O(N*Log(N))
Space Complexity: O(1)

Solution 4:

Solution 5:

Reference

https://www.geeksforgeeks.org/longest-common-prefix-using-sorting/

Follow-up: