Simple 7 line Python solution with `filter`

  • -1
    def longestCommonPrefix(self, strs):
        :type strs: List[str]
        :rtype: str
        if len(strs) == 0:
            return ''
        strings = sorted(strs, key=len)
        for i in range(len(strings[0]), 0, -1):
            if len(strings) == len(filter(lambda x: x[:i] == strings[0][:i], strings)):
                return strings[0][:i]
        return ''

    We can base our search off the shortest string in the list. We successively try to check if the prefix of all the strings is equal to the shortest string, deducting from the shortest string for each failure.

    I believe the runtime is:

    O(nlogn) [to sort] + O(m * n) [m is the length of the shortest string, n is the length of the list]

    therefore, O(n^2) overall

Log in to reply

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