Python binary search O(klog(nk)) 135ms


  • 0
    Y

    Assuming the length of each word in dictionary is a constant, the time complexity is O(klog(k)) for sorting and O(klog(n)) for searching.

        def findLongestWord(self, s, d):
            import bisect
            def issub(alpha, string):
                i = -1
                for char in string:
                    c = alpha[ord(char) - 97]
                    index = bisect.bisect_right(c, i)
                    try:
                        i = c[index]
                    except IndexError:
                        return False
                return True
                
            alpha = [[] for i in range(26)]
            for i, char in enumerate(s):
                alpha[ord(char) - 97].append(i)
            d.sort(key = lambda x: (-len(x), x))
            for string in d:
                if issub(alpha, string):
                    return string
            return ''
    

Log in to reply
 

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