• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Store all words in a Trie into a list

 
Greenhorn
Posts: 11
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I'm trying to implement a method that will store all words in a Trie data structure in a List.
This is my Node class:

I am using a HashMap to store the child characters as keys and the child nodes as values. A node that completes a word will have the field isCompleteWord set to true.
Methods to add all words to a List:


Currently if I have stored in the Trie the words "beard", "bold", "brew", when I print the list of words starting with the prefix "b", I get:

What I was expecting:

I think I need a way for the String word to be reset whenever I have found a word, instead of the next characters being appended.
 
Ranch Hand
Posts: 127
2
Monad Java Linux
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I've worked with(played with simple trie's) trie's in other languages(JavaScript, OCaml) and retrieving the original strings or remainder of strings should be a simple recursive function that builds each string and then stores each completed string in some data store.

In JavaScript its done with a simple function like:


You would probably derive zero information from the OCaml example so I'll skip it.
 
Marshal
Posts: 79180
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Both of you, welcome to the Ranch
 
Gerard Gauthier
Ranch Hand
Posts: 127
2
Monad Java Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I tried putting my 1 week of Java experience to work.. Here's what I produced... My apologies to any competent Java programmers.

First split up a string into first character and remainder or produce empty fields with Optional.


Second check string length and split it up.


Third(this code could really be cleaned up a bit) the Trie.


The above will store and retrieve from the Trie.
 
Don't get me started about those stupid light bulbs.
reply
    Bookmark Topic Watch Topic
  • New Topic