So I have a trie in python but its not leading to the runtime complexity I want from my algorithm to find compound words. I was originally trying to use this algorithm but had no luck https://stackoverflow.com/questions/1291734/finding-dictionary-words
So the words are
['bye','byeen','s','byeens'] # My Trie (*) denotes a word ending # b - y - e* - e - n* - s* , s*
My algorithm checks the word byeens in the trie and if it exists and then checks if all the individual words exist
So it checks if
'Bye' exists, 'en' exists, and 's' exists. When checking if 'Byeens' is a compound word
While this works for most situations. It obviously doesnt work for this one. The way I found to remedy this is when checking the trie for byeens it constructs two different paths to check if either exist
['bye','en','s'] # doesnt exist ['byeens','s'] # does exist
However, what if the trie is composed of all a's? like this for example
this gets big... really fast. To the order of 2^m-1 where m is the length of the word I believe.
Anyone found a better way to do this?