5 ms·
I'm not seeing how a bloom filter would help you here. The only application of a bloom filter that I can see is checking whether or not the word candidate you g
by buss 14y ago
I'm not seeing how a bloom filter would help you here. The only application of a bloom filter that I can see is checking whether or not the word candidate you generated is in a dictionary. All n-choose-k sets is enormous and you'd spend a very long time just generating the candidates.
A prefix trie, as the GP mentioned, seems like a very good and obvious approach. You avoid most of the work generating non-words because all paths lead to complete words unless you run out of letters and you're not on a terminal.
What do you gain from the bloom filter?
- buss 14y agoOn further thought, you could use a bloom filter to test if a given set of letters has any valid words, then look up that set in a normal hash table (or use an associate bloom filter). I haven't done any calculations or experiments, but it doesn't seem like you'd save much computation time with the bloom filter vs just using a hash table that maps (letter sets) -> (words). I could see this being faster than a trie, though, since you aren't trying to do spelling suggestions and you lose a lot of time traversing the trie for all possible permutations of the letters.
- baddox 14y agoI suspect zwily was talking about the word verification for the Letterpress app itself, not the cheating app.
- zwily 14y agoRight - just for verification in Letterpress. The occasional false positive wouldn't be so bad, and you can tune your bloom filter so that it's really rare.