Trie

Hash map Trie

Pinterest LinkedIn Tumblr

A hash array based trie is an implementation of an associative array that combines the characteristics of a hash table and an array mapped trie. Write program to implement the hash map based trie

Algorithm Explanation

Construct an array and pass to the utility function.
Add function takes the string and add the string value to the hash map. If the hash map contains the key, assign the current node with the object. Otherwise, put the current node with given hash map.
Contains function checks the given key is available in the hash map. If it contains, return the value. Otherwise, returns false.

Source Code

package com.dsacode.DataStructre.trie;
 
import java.util.Arrays;
import java.util.Collection;
import java.util.HashMap;
 
public class HashmapTrie {
 
    @SuppressWarnings("rawtypes")
    HashMap < Character, HashMap > root= new HashMap < Character, HashMap > ();
      
    public HashmapTrie(){
         
    }
     
    public HashmapTrie(String[] sa) {
        addAll(sa);
    }
  
    @SuppressWarnings({ "rawtypes", "unchecked" })
    public void add(String s) {
        HashMap < Character, HashMap > curr_node = root;
        for (int i = 0, n = s.length(); i < n; i++) {
            Character c = s.charAt(i);
            if (curr_node.containsKey(c))
                curr_node = curr_node.get(c);
            else {
                curr_node.put(c, new HashMap < Character, HashMap >());
                curr_node = curr_node.get(c);
            }
        }
        curr_node.put('\0', new HashMap < Character, HashMap >(0));
    }
  
 
    public void addAll(String[] sa) {
        for (String s: sa)
            add(s);
    }
  
    public void addAll(Collection < String > sc) {
        for (String s: sc)
            add(s);
    }
  
   
    @SuppressWarnings({ "rawtypes", "unchecked" })
    public boolean contains(String s) {
        HashMap < Character, HashMap > curr_node = root;
        for (int i = 0, n = s.length(); i < n; i++) {
            Character c = s.charAt(i);
            if (curr_node.containsKey(c))
                curr_node = curr_node.get(c);
            else
                return false;
        }
        if (curr_node.containsKey('\0'))
            return true;
        else
            return false;
    }
  
    public static void main(String[] args) {
        HashmapTrie t = new HashmapTrie();
        String []ara={"Helloo","Hell","Help"};
        System.out.println("Add strings to the hashmap based trie");
         
        for(String str: ara)
            t.add(str);
        System.out.println("Strings in Array:"+Arrays.toString(ara));
         
        System.out.println("Check 'Hell' in Trie:"+ t.contains("Hell")  );
        System.out.println("Check 'Hello' in Trie:"+ t.contains("Hello")  );
        System.out.println("Check 'Helps' in Trie:"+ t.contains("Helps")  );
         
    }
 
}

Output

Add strings to the hash map based trie
Strings in Array: [Helloo, Hell, Help]
Check 'Hell' in Trie: true
Check 'Hello' in Trie: false
Check 'Helps' in Trie: false

Write A Comment