BFS


  • 0
    S
    class Solution(object):
        def longestWord(self, words):
            """
            :type words: List[str]
            :rtype: str
            """
            if not words:
                return ''
            # O( m x log(m)) where m are single character words
            queue   = collections.deque(sorted([word for word in words if len(word) == 1])) 
            maxlen  = 0
            maxword = ''
            wordset = set(words)
            while queue: # O(N^2) where N is length longest word
                word = queue.popleft() # O(1)
                for c in 'abcdefghijklmnopqrstuvwxyz': # O(26)
                    if word + c in wordset: # O(1)
                        queue += (word+c),  # O(1)
                if len(word) > maxlen:      # O(1)
                    maxlen  = len(word)     # O(1)
                    maxword = word          # O(1)
            return maxword
    

Log in to reply
 

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