Zip function 5 lines O(min(lengths of strs))

  • 1
    def longestCommonPrefix(strs):
            len_lcp = 0
            for letters in zip(*strs):
                if len(set(letters)) > 1: break
                len_lcp += 1
            return '' if not strs else strs[0][:len_lcp]

    zip function builds tuples of letters at same index in all strings and stops when one string has no more letter.

  • 4

    Good idea, but the running time is O(min(len) * n) where n is the number of strings in strs, not simply O(min(len)).

    That is because letters has length n and therefore the condition len(set(letters)) > 1 needs O(n) time to calculate.

Log in to reply

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