/**
*
*/
package com.kant.amazon;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
/**
* @author shashi
*
*/
public class TrieBasedDictionary {
TrieNode root;
public TrieBasedDictionary() {
root = new TrieNode();
}
/**
*
* @param items
*/
public void addWordsFromList(List<String> items) {
for (String item : items) {
String[] keyVal = item.split(":");
root.addWord(keyVal[0], keyVal[1]);
}
}
public String findWordMeaning(String text) {
return root.findWordMeaning(text.toUpperCase());
}
/**
*
* @param text
* @return
*/
public boolean hasPrefix(String text) {
return root.isValidPrefix(text);
}
/**
*
* @param args
*/
public static void main(String[] args) {
TrieBasedDictionary dictionary = new TrieBasedDictionary();
List<String> words = new ArrayList<>();
words.add("AGNOSTIC:someone who believes that it is impossible to know whether there is a God or not.");
words.add("ALOOF:being distant in manner or feeling, unsympathetic");
words.add("BONA FIDE:a gesture made in good faith ");
words.add("CAVEAT:a warning or caution given");
words.add("DESPICABLE:deserving of contempt");
dictionary.addWordsFromList(words);
System.out.println(dictionary.hasPrefix("BONA "));
System.out.println(dictionary.findWordMeaning("BONA FIDE"));
}
}
/**
*
* @author shashi
*
*/
class TrieNode {
TrieNode[] children;
boolean isAWord;
int countPrefixes; // number of prefixes has this node.
String meaning; // meaning of word
public TrieNode() {
countPrefixes = 0;
isAWord = false;
children = new TrieNode[255];
Arrays.fill(children, null);
meaning = null;
}
/**
*
* @param input
* @param meaning
*/
public void addWord(String input, String meaning) {
if (input.isEmpty()) {
this.meaning = meaning;
this.isAWord = true;
return;
}
countPrefixes++;
int first = input.charAt(0);
if (children[first] == null) {
children[first] = new TrieNode();
}
children[first].addWord(input.substring(1), meaning);
}
/**
*
* @param key
* @return
*/
public String findWordMeaning(String key) {
if (key != null) {
if (key.isEmpty()) {
if (isAWord) {
return meaning;
}
System.out.println("word not found");
return null;
}
int first = key.charAt(0);
if (children[first] != null) {
return children[first].findWordMeaning(key.substring(1));
}
}
return null;
}
/**
*
* @param text
* @return
*/
public boolean isValidPrefix(String text) {
if (text != null) {
if (text.isEmpty())
return true;
int first = text.charAt(0);
if (children[first] != null) {
if (text.length() == 1) {
return true;
}
return children[first].isValidPrefix(text.substring(1));
}
}
return false;
}
}