Divide-and-Conquer Approach, python, 44ms

  • 0
    class Solution:
        # @param {string[]} strs
        # @return {string}
        def longestCommonPrefix(self, strs):
            if not strs: return ""
            total = len(strs)
            l = min([len(x) for x in strs])
            g = 2
            while g / 2 < total:
                for i in xrange((total+g-1)/g):
                    if i*g+g/2 < total:
                        while l and strs[i*g][:l] != strs[i*g+g/2][:l]: l-=1
                g *= 2
            return strs[0][:l]

Log in to reply

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