Easy Python | 100% Speed | Highly Optimized
Easy Python | 100% Speed | Highly Optimized\n\nThe Python code below corresponds to a simple solution based on:\n\n1. Matching substrings against a global set (
**Easy Python | 100% Speed | Highly Optimized**\n\nThe Python code below corresponds to a simple solution based on:\n\n1. Matching substrings against a global set (I experimented using "Tries" originally, but they don\'t provide any benefits).\n\n2. Using Binary Search to look for compatible substring lengths (the process is still O(n), but it\'s a significant boost).\n\n3. Using Depth-First Search to look for complete matches for a word.\n\nThe comments inside the code provide further insights. I hope you find it helpful. Cheers,\n\nPS. Those notes about bisect_right, and bisect_left changed my life lol\n```\n# Python 2/3\nfrom bisect import bisect_right,bisect_left\nclass Solution:\n    def findAllConcatenatedWordsInADict(self, words):\n        words = set([word for word in words if word]) # Filter Empty Words\n        #\n        # Find Compatible substring lengths using binary search\n        nlens = sorted( set(map(len,words)) )\n        def getsizes(L,i):\n            # BISECT USAGE:\n            #     bisect_left   ->  a[lo:i] <  x <= a[i:hi]\n            #     bisect_right  ->  a[lo:i] <= x <  a[i:hi]\n            if i:\n                Lj = bisect_right(nlens,L) # include L\n            else:\n                Lj = bisect_left(nlens,L) # exclude L\n            # Yield Reversed without delay\n            for j in range(Lj-1,-1,-1):\n                yield nlens[j]\n        #\n        # DFS matching function:\n        def dfs(i,word,L):\n            if i == L:\n                return True\n            #\n            for a in getsizes(L-i,i):\n                if word[i:i+a] in words and dfs(i+a,word,L):\n                    return True\n            return False\n        #\n        # Final Loop:\n        res = []\n        for word in words:\n            if dfs(0,word,len(word)):\n                res.append(word)\n        #\n        return res\n```
['Python', 'Python3']