Simple Python solution


  • 42
    S

    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[0][:i]
            else:
                return min(strs)

  • 40
    A

    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)

  • 2
    T

    Same method as yours and I just learned the use of reduce.


  • 0
    Z

    easy to understand!


  • 1
    5

    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?


  • 5
    Q

    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 ""

  • 0
    Q

    the last line could be

    return min(strs, key=len)

  • 0
    S

    what's the time complexity of 's,t = t,s'?


  • 1
    G

    Constant time.
    It is just like swapping pointers.


  • 0
    S

    OK~thanks for your reply.


  • 0
    M

    @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:
    break
    prefix +=values[0]
    return prefix


  • 3
    F

    @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[0][:l]
                    l += 1
            return strs[0][:l]
    

  • 0

    amazing solution !!!


  • 0
    Q

    @alexkyllo Nice! though I've never used reduce() before~


  • 0
    T

    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

  • 0
    T

    @fschaffa
    l+=1 should have the same indent with if len(set(cg) ...


  • 0
    Y

    input: ['atcg', 'ag', 'cg']
    output: ''
    It should be 'g'.


  • 0
    S

    @Yang.X.X
    You seem to be solving for longest common suffix (end of word). Prefix starts at the beginning of the word.


  • 0
    R

    @alexkyllo I'm a beginner in Python.Your solution is easy to understand.Thank you!


  • 0
    B

    I feel that I am right, but I submit solution ,the system prompts "Line 14: UnboundLocalError: local variable 'lcp' referenced before assignment".Who can help me ?please

    class Solution(object):
        def longestCommonPrefix(self, strs):
            if not strs:
                return ''      
            for g in range(0,len(strs)-1):
                t = strs[g]
                lcp=''
                for i in range(0,len(strs[0])-1):
                    if t[i]==strs[g+1][i]:
                        lcp=lcp+t[i]
                    else:
                        break
                t=lcp
            return lcp
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.