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
1 Comment
I love what you guys are up too. This type of clever work and reporting!
Keep up the wonderful works guys I’ve incorporated you guys to my own blogroll.