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 "".
LeetCode Solutions1 <= strs.length <= 2000 <= strs[i].length <= 200strs[i] consists of only lowercase English letters if it is non-empty.Where S is the sum of all characters in all strings in the array, n is the number of strings, and m is the length of the longest string. In the worst case, all strings are the same and we compare each character of each string with the prefix.
We are only using a constant amount of extra space for the prefix variable.
The horizontal scanning approach starts by assuming the longest common prefix is the first string in the array. Then, it iterates through the remaining strings and checks if they start with the current prefix. If a string does not start with the prefix, the prefix is shortened by removing the last character until a common prefix is found or the prefix becomes empty.
Where S is the sum of all characters in all strings in the array, n is the number of strings, and m is the length of the longest string. In the worst case, all strings are the same and we compare each character of each string with the first string.
We are only using a constant amount of extra space for the character variable c and the index variable i.
The vertical scanning approach checks each character of the first string against the corresponding characters of the other strings. If a mismatch is found or if any string is shorter than the current index, the function returns the common prefix up to that point.
Where n is the number of strings and m is the length of the longest string. Sorting the array takes time, and comparing the first and last strings takes time.
We are only using a constant amount of extra space for the index variable i and the references to the first and last strings. The sorting operation may require space depending on the sorting algorithm used, but it is generally considered for in-place sorting algorithms.
By sorting the array of strings, the longest common prefix of the entire array must be a prefix of the first and last strings in the sorted order. Therefore, we only need to compare the first and last strings character by character until they differ to find the longest common prefix.
| Approach | Rating | Time Complexity | Space Complexity | Advantages | Disadvantages |
|---|---|---|---|---|---|
| Horizontal Scanning | Simple and intuitive — progressively shrinks the prefix | May do unnecessary comparisons if early strings don't share prefix | |||
| Vertical Scanning | Efficient early termination when strings differ early | Slightly more complex nested loop structure | |||
| Sorting Trick | Only needs to compare first and last strings after sorting | Sorting overhead makes it slower than linear approaches |
The optimal approach for this problem is Solution 1: Horizontal Scanning, which achieves time complexity and space complexity. It starts with the first string as the prefix and progressively shortens it by comparing against each subsequent string, making it the most straightforward and efficient approach.
class Solution: def longestCommonPrefix(self, strs: List[str]) -> str: if len(strs) == 0: return ""
prefix = strs[0]
for s in strs[1:]: # loop through the strings starting from the second string while prefix != s[0:len(prefix)]: # check s starts with prefix, can replace with "while not s.startswith(prefix):" prefix = prefix[:-1] # remove the last character from prefix
if len(prefix) == 0: return ""
return prefixclass Solution: def longestCommonPrefix(self, strs: List[str]) -> str: if len(strs) == 0: return ""
for i in range(len(strs[0])): # loop through the characters of the first string c = strs[0][i] # get the current character of the first string
for s in strs[1:]: # loop through the strings starting from the second string # if the current string is shorter than the current index or the current character does not match, return the common prefix up to the current index if len(s) <= i or s[i] != c: return strs[0][:i]
return strs[0]class Solution: def longestCommonPrefix(self, strs: List[str]) -> str: if len(strs) == 0: return ""
# Sort the array to bring similar prefixes together strs.sort()
first = strs[0] last = strs[-1]
i = 0 # Compare the first and last strings character by character until they differ while i < len(first) and i < len (last) and first[i] == last[i]: i += 1
return first[:i]