Simple 7 line Python solution with `filter`


  • -1
    K
    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.