python DFS solution


  • 0
    L

    One tip to pass TLE: when test if one word can be contact by more than two words in the list, using the min-len word length and length-min_len to prune the dfs to pas the large test case

    from collections import defaultdict
    
    
    class Solution(object):
        def findAllConcatenatedWordsInADict(self, words):
            """
            :type words: List[str]
            :rtype: List[str]
            """
            res = []
            words = set(words)
            min_len = float("inf")
            for word in words:
                min_len = min(len(word), min_len)
            for word in words:
                l, r = min_len, len(word) - min_len
                if len(word)>0 and self.valid(words, l, r, word, 0, 0):
                    res.append(word)
            return res
    
        def valid(self, words, l, r, w, index, num):
            if index == len(w) and num > 0:
                return True
            if index + l <= len(w):
                for i in xrange(index + l, min(index + r, len(w)) + 1):
                    if w[index:i] in words:
                        if self.valid(words, l, r, w, i, num + 1):
                            return True
            return False
    

Log in to reply
 

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