Dictionary using Trie

Dictionary is the data structure that maps keys to values. Write a program to implement Dictionary.

Algorithm Explanation

	Dictionary is an abstract data type. It constructed using key and value pairs. The key does not duplicate.
	Dictionary implementation uses HashMap to store the values and keys.
	Insert operation inserts the string into the hashmap and uses insert word operation internally.
	Search operation takes the key string and search in the hash map. The internal operation takes the node Dictionary and checks the end of the word.

Source Code

package com.dsacode.DataStructre.trie;
 
import java.util.HashMap;
import java.util.Map.Entry;
 
class NodeDictionary {
    public NodeDictionary parent;
    public Boolean endOfWord = false;
    public HashMap < Character, NodeDictionary > children = new HashMap < Character, NodeDictionary > ();
     
    public String toString(){
        String str="";
        for (Entry < Character, NodeDictionary > entry : children.entrySet()) {
            Character key = entry.getKey();
            NodeDictionary value = entry.getValue();
                str += "Key:"+key+" Value:"+value.toString();
            }
        return str;
    }
}
 
public class DictionaryHashMap {
private HashMap < Character, NodeDictionary > roots = new HashMap < Character, NodeDictionary >();
     
    public boolean search(String string) {
        if (roots.containsKey(string.charAt(0))) {
            if (string.length()==1 && roots.get(string.charAt(0)).endOfWord) {
                return true;
            }
            return searchFor(string.substring(1),roots.get(string.charAt(0)));
        } else {
            return false;
        }  
    }
     
    public void insert(String string) {
        if (!roots.containsKey(string.charAt(0))) {
            roots.put(string.charAt(0), new NodeDictionary());
        }
         
        insertWord(string.substring(1),roots.get(string.charAt(0)));
    }
     
    private void insertWord(String string, NodeDictionary node) {
        final NodeDictionary nextChild;
        if (node.children.containsKey(string.charAt(0))) {
            nextChild = node.children.get(string.charAt(0));
        } else {
            nextChild = new NodeDictionary();
            node.children.put(string.charAt(0), nextChild);
        }
                 
        if (string.length() == 1) {
            nextChild.endOfWord = true;
            return;
        } else {
            insertWord(string.substring(1),nextChild);
        }
    }
     
    private boolean searchFor(String string, NodeDictionary node) {
        if (string.length()==0) {
            if (node.endOfWord) {
                return true;
            } else {
                return false;
            }
        }
         
        if (node.children.containsKey(string.charAt(0))) {
            return searchFor(string.substring(1),node.children.get(string.charAt(0)));
        } else {
            return false;
        }
    }
    public static void main(String[] args) {
        DictionaryHashMap d = new DictionaryHashMap();
         
        System.out.println("Insert the words: 'Hello', 'world', 'Apple', 'Orange'");
        d.insert("Hello");
        d.insert("world");
        d.insert("Apple");
        d.insert("Orange");
         
        System.out.println("Search 'Apple' in trie: "+d.search("Apple"));
         
        System.out.println("Search 'Hel' in trie: "+d.search("Hel"));
 
    }
 
}

Output

Insert the words: 'Hello', 'world', 'Apple', 'Orange'
Search 'Apple' in trie: true
Search 'Hel' in trie: false