CODEWITHSUNDEEP
javastringrecursiontrie
Haque1
Haque1

Reputation: 593

Java: Storing Substrings in a Trie

I'm implementing a trie which will store both the substrings and their number of occurrence in a string. Each node in my trie will have a Map called children, which will store any subnodes of the main node.

My problem is that eventually, those subnodes will have subnodes of their own and I don't know how I will be able to retrieve data from "a map within a map within a map..." so to speak.

Here's what I have so far:

private class TrieNode
{
    private T data; //will hold the substring
    int count; //how many occurrences of it were in the string
    private Map<TrieNode, Integer> children; //will hold subnodes
    private boolean isWord; //marks the end of a word if a substring is the last substring of a String

    private TrieNode(T data)
    {
        this.data = data;
        count = 1;
        children = new HashMap<TrieNode, Integer>();
        isWord = false;
    }
}

How do I retrieve data from the subnodes, who might themselves have other subnodes beneath them?

P.S. I apologize if I wasn't able to explain it clearly enough- I'm having problems with recursion. Thanks.

Upvotes: 0

Views: 479

Answers (2)

ILMTitan
ILMTitan

Reputation: 11027

You need a few things. First of all, you want Map<T, TrieNode> because you are mapping a piece of data to a sub-Trie.

Secondly, you need to know how to split your data into a head and a tail, and how to recombine them later. In the standard case of strings, you use substring and concationation. For instance:

private TrieNode(String currChar, String rest) {
   this.data = currChar;
   this.children = new HashMap<String, TrieNode>();
   if(rest.isEmpty()) {
      this.isWord = true;
   } else {
      String head = rest.substring(0, 1);
      String tail = rest.substring(1, rest.length());
      this.children.add(head, new TrieNode(head, tail);
   }
}

Your T needs to be able to do something similar, or using a Trie in the first place does not make sense.

Additionally, you rarely need to recompile a string from a Trie. Usually, you are just checking if a string exists in a Trie, or how many strings something is a substring of.

Upvotes: 1

Marko Topolnik
Marko Topolnik

Reputation: 200166

I don't see why you'd store a string in a type called T. That sounds like a generic type, but you haven't declared it on the class.

Anyway, I presume you'll need a Map<T, TrieNode> that will hold each child keyed by its substring. That way you recur into another TrieNode, which again has another map of the same kind.

Upvotes: 1

Related Questions