Dictionary is an abstract data type composed of a collection of keys and values. The Dictionary does not take duplicate keys and must write to handle collisions that occur when two keys are mapped to same index.
Write a program to look up the item from the hash tables. Value can be duplicated and keys should not duplicate.
source Code
package com.dsacode.Algorithm.search; import java.util.ArrayList; import java.util.HashSet; import java.util.List; import java.util.Set; import java.util.Stack; public class DictionaryLookup { public static void main(String[] args) { Set < String > dictionary = new HashSet < String >(); dictionary.add("Hello"); dictionary.add("HelloWorld"); dictionary.add("Hellosiva"); dictionary.add("Hello"); dictionary.add("Helo"); dictionary.add("Hllo"); System.out.print("Items in the dictionary: ["); for (String s : dictionary) { System.out.print(s+","); } System.out.print("]\n"); String input = "Hello"; List < List < String > > results = new ArrayList < List < String > >(); System.out.print("Search 'Hello' string from the dictionary: "); search(input, dictionary, new Stack < String >(), results); for (List < String > result : results) { for (String word : result) { System.out.print(word + " "); } System.out.println("(" + result.size() + " words)"); } System.out.println(); } public static void search(String input, Set < String > dictionary, Stack < String > words, List < List < String > > results) { for (int i = 0; i < input.length(); i++) { String substring = input.substring(0, i + 1); if (dictionary.contains(substring)) { words.push(substring); if (i == input.length() - 1) { results.add(new ArrayList < String >(words)); } else { search(input.substring(i + 1), dictionary, words, results); } words.pop(); } } } }
Output
Items in the dictionary: [Helo,Hello,Hllo,Hellosiva,HelloWorld,] Search 'Hello' string from the dictionary: Hello (1 words)
Algorithm Explanation
![]() | The predefined dictionary has set of words. |
![]() | Take user input and split the string into tokens. |
![]() | Search a dictionary for the words in the key string. If it matches, add to the result. |
Time Complexity
Best Case | Average Case | Worst Case |
---|---|---|
O(1) | O(1) | O(n) |