undefined | Better HN

0 pointskragen14y ago0 comments

I suppose that depends on what you store in your trie. If every node contains a field for the length of the longest path below it, then yes. But that's not a normal thing to store in a trie, and it wasn't at all obvious to me that that was what you meant.

0 comments

btilly14y ago

Not true.

If you keep on following the trie, you'll fall out of the trie at the point that there are no words that have that sequence at the start. Which will happen by the time you exceed the longest word in the dictionary, but will probably happen substantially before that.

dtunkelang14y ago

Am curious to see having the dictionary in a trie allows you to build an implementation that is O(n). Will add it to the blog post if it works.

j / k navigate · click thread line to collapse

0 pointskragen14y ago0 comments

0 comments

btilly14y ago

Not true.

dtunkelang14y ago

Am curious to see having the dictionary in a trie allows you to build an implementation that is O(n). Will add it to the blog post if it works.

j / k navigate · click thread line to collapse