0
$\begingroup$

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

a*-a*-a*-a*-a*

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?

$\endgroup$
  • 1
    $\begingroup$ Python is offtopic here. What is the problem you are trying to solve? What is the (idea of) your algorithm? $\endgroup$ – Raphael Oct 4 '16 at 7:13
  • $\begingroup$ I can't understand the idea behind your algorithm. Can you give pseudocode describing your data structure & algorithm? Can you draw a picture to show the structure of your trie? I don't know what b - y - e* - e - n* - s* , s* or a*-a*-a*-a*-a* means. Aside from your current approach, what problem exactly are you trying to solve? Can you give a self-contained specification of the problem, explained independently of your approach? $\endgroup$ – D.W. Oct 5 '16 at 4:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.