Python O(nw^2) DP + trie


  • 0
    X

    time complexity O(nw^2): w is the average word width.

    class Solution(object):
        def findAllConcatenatedWordsInADict(self, words):
            """
            :type words: List[str]
            :rtype: List[str]
            """
            def IsConcat(trie, w):
                sz = len(w)
                dp = [False] * (sz+1)
                dp[0] = True
                for lo in range(sz):
                    if dp[lo] == False:
                        continue
                    for hi, _ in prefixs(trie, w, lo):
                        dp[hi] = True
                    if dp[-1]:
                        return True
                return False
                        
            def concatwords(words):
                words = sorted(words, key=len, reverse=True)
                trie = {}
                while words:
                    w = words.pop()
                    if IsConcat(trie, w):
                        yield w
                    insert(trie, w)
            return list(concatwords(words))
            
    def insert(trie, w):
        for c in w:
            trie = trie.setdefault(c, {})
        trie[None] = w
    
    def prefixs(trie, w, lo):
        for i in range(lo, len(w)):
            trie = trie.get(w[i])
            if trie is None:
                break
            prefix = trie.get(None)
            if prefix: 
                yield i+1, prefix           
    

Log in to reply
 

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