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.
Constraints:
0 <= strs.length <= 2000 <= strs[i].length <= 200strs[i] consists of only lower-case English letters.Source
def longest_common_prefix(strs):
"""Vertical scanning."""
if not strs:
return ""
prefix = min(strs, key=len)
for i, char in enumerate(prefix):
for word in strs:
if word[i] != char:
return prefix[:i]
return prefix
from functools import reduce
def longest_common_prefix(strs):
"""Horizontal scanning using reduce
Time complexity : O(S) (s: m*n - sum of all letters, in worst case all words have same lenghts)
Space complexity : O(1)
"""
def merge(str1, str2):
i = 0
while i < len(str1) and i < len(str2) and str1[i] == str2[i]:
i += 1
return str1[:i]
if not strs:
return ""
return reduce(merge, strs) # merge the longest common prefix in first 2 words, then reduce with others
def longest_common_prefix(strs):
"""Using a set of i-th letter of each word."""
prefix = ''
for column_slice in zip(*strs): # tuples of all i-th letter of each word (up to len() of smallest word)
if len(set(column_slice)) == 1: # if the set only contains 1 element = same letter
prefix += column_slice[0]
else:
break
return prefix
strs = ["flower", "flow", "flight"]
longest_common_prefix(strs)
'fl'
strs = ["dog", "racecar", "car"]
longest_common_prefix(strs)
''
strs = ["cir", "car"]
longest_common_prefix(strs)
'c'
strs = ["cat"]
longest_common_prefix(strs)
'cat'
strs = []
longest_common_prefix(strs)
''
Could you solve it using the following implementation:
def longest_common_prefix(strs):
"""Using Divide and Conquer"""
pass
def longest_common_prefix(strs):
"""Using Binary Search"""
pass
def longest_common_prefix(strs):
"""Using Trie"""
pass