Longest Common Prefix using Binary Search

longest_common_prefix.py

class Solution:
    def isLCP(self, strs, k):
        return len(set([s[:k] for s in strs])) == 1

    def longest_common_prefix(self, strs):
        n = len(strs)
        if n == 0:
            return ""
        beg = 0
        end = min([len(s) for s in strs])
        while beg <= end:
            mid = (beg + end) // 2
            currval = self.isLCP(strs, mid)
            nextval = self.isLCP(strs, mid + 1)
            if (currval and not nextval) or mid >= end:
                return strs[0][:mid]
            elif beg == end:
                break
            elif currval and nextval:
                beg = mid + 1
            else:
                end = mid
        return ""