Might be a bit slow, but here's my relatively elegant Python solution:
class Solution: # @return a string def longestCommonPrefix(self, strs): if not strs: return "" for i, letter_group in enumerate(zip(*strs)): if len(set(letter_group)) > 1: return strs[:i] else: return min(strs)
Nice use of zip.
Here's my version, it ran in 58 ms. I was proud of myself for using reduce() appropriately:
class Solution: def lcp(self, str1, str2): i = 0 while (i < len(str1) and i < len(str2)): if str1[i] == str2[i]: i = i+1 else: break return str1[:i] # @return a string def longestCommonPrefix(self, strs): if not strs: return '' else: return reduce(self.lcp,strs)
What is 'min(strs)' stand for. It's won't the shortest string in the list. It will return the lowest alphabetical order string.
e.g. min(['z','abc']) = 'abc
Is this correct?
thanks very much, I try to rewrite your idea in below.
def longestCommonPrefix(self, strs): def lcp(s, t): if len(s)>len(t): s, t = t, s for i in range(len(s)): if s[i]!=t[i]: return s[:i] return s return reduce(lcp,strs) if strs else ""
@syrupmachine Great use of zip.. I came up with a similar solution as well
prefix = ""
for values in zip(*strs):
if len(set(values)) >1:
@syrupmachine a small modification that avoids the min() when all substrings match:
def longestCommonPrefix(self, strs): """ :type strs: List[str] :rtype: str """ if not strs: return '' l = 0 for cg in zip(*strs): if len(set(cg)) > 1: return strs[:l] l += 1 return strs[:l]
@alexkyllo Nice! though I've never used reduce() before~
This is a quite easy to understand version.
def longestCommonPrefix(self, strs): """ :type strs: List[str] :rtype: str """ n = 0 str_out = "" length = 0 for i in strs: length = max(len(i), length) while n < length: try: a = set([i[n] for i in strs]) n += 1 if len(a) > 1: return str_out elif len(a) == 1: for i in a: str_out += i except: return str_out return str_out
l+=1 should have the same indent with if len(set(cg) ...
You seem to be solving for longest common suffix (end of word). Prefix starts at the beginning of the word.
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.