Creating & searching the word in dictionary.
You might be hearing or reading to use Tries or Ternary Search Tree, for having dictionary kind of structure.
These seem to be find if having certain kind of words but I don't feel that these will be fine to develop dictionary as we will need to customize it. So I just thought to try these using Tree, Node & HashMap, as shown below. Though it may not be working extensively but I think, it can be used to further enhance this approach to cover other scenarios. Will be happy to know your views.
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
public class Dictionary {
private static HashMap<Character, Integer> positions;
private static ArrayList<Character> characters;
private static HashMap<Character, NodeW<Character>> dictionary;
private static int count;
public static void main(String[] args) {
new Dictionary();
ArrayList<String> words = new ArrayList<>();
words.add("abc");
words.add("bdc");
words.add("bcadgh");
words.add("bca");
words.add("bcaagh");
words.add("bych");
words.add("cbaeft");
makeDictionary(words);
System.out.println("Number of distinct starting characters in dictionary : " + dictionary.size());
System.out.println("Is available? " +
isWord("bcadgh"));
ArrayList<String> results = new ArrayList<>();
wordStartingFrom('a', results);
System.out.println("Words starting from 'a' : ");
results.forEach(System.out::println);
System.out.println("Total number of words in dictionary : " + count);
}
/**
* Finds the words starting from the given character.
* @param ch
* @param results
*/
private static void wordStartingFrom(Character ch, ArrayList<String> results) {
NodeW<Character> node = dictionary.get(ch);
StringBuilder sb = new StringBuilder();
if(node != null) {
sb.append(ch);
List<NodeW<Character>> list = getOrderedNext(node);
for(NodeW<Character> child : list) {
if(child != null)
sb.append(child.data);
if(child != null && child.isWord)
results.add(sb.toString());
node = child;
wordHavingChar(node, results, sb);
sb = new StringBuilder();
sb.append(ch);
}
node = null;
}
}
/**
* Finds the words starting from the given node.
* @param node
* @param results
* @param sb
*/
private static void wordHavingChar(NodeW<Character> node, ArrayList<String> results, StringBuilder sb) {
while(node != null) {
List<NodeW<Character>> list = getOrderedNext(node);
if(list.isEmpty())
node = null;
for(NodeW<Character> child : list) {
StringBuilder sb1 = new StringBuilder();
sb1.append(sb);
if(child != null)
sb.append(child.data);
if(child != null && child.isWord)
results.add(sb.toString());
node = child;
wordHavingChar(node, results, sb);
sb = sb1;
}
node = null;
}
}
/**
* Gets the sorted list of nodes next to the given node in the dictionary.
* @param node
* @return
*/
private static List<NodeW<Character>> getOrderedNext(NodeW<Character> node) {
List<NodeW<Character>> results = new ArrayList<>();
Character chars = node.data;
int pos = positions.get(chars);
List<Character> before = characters.subList(0, pos+1);
for(Character ch : before) {
if(node.previous.containsKey(ch))
results.add(node.previous.get(ch));
else if(node.eq != null && node.eq.data == ch)
results.add(node.eq);
}
List<Character> after = characters.subList(pos+1, 26);
for(Character ch : after) {
if(node.next.containsKey(ch))
results.add(node.next.get(ch));
}
return results;
}
/**
* Checks if the given word exists in the dictionary.
* @param word
* @return
*/
private static boolean isWord(String word) {
int len = word.length();
int i = 1;
NodeW<Character> node = dictionary.get(word.charAt(0));
while(i < len && node != null) {
node = getNextNode(word.charAt(i), node);
if(i == len-1 && node != null && node.isWord)
return true;
i++;
}
return false;
}
/**
* Gets the next node containing the given character, else null is returned.
* @param ch
* @param node
* @return
*/
private static NodeW<Character> getNextNode(Character ch, NodeW<Character> node) {
if(node.data == ch)
return node.eq;
else if(node.data > ch)
return node.previous.get(ch);
else
return node.next.get(ch);
}
/**
* Creates the dictionary in memory from the given list of words.
* @param words
*/
private static void makeDictionary(ArrayList<String> words) {
words.forEach( word -> {
int len = word.length();
NodeW<Character> node = dictionary.get(word.charAt(0));
if(node == null) {
node = new NodeW<>();
node.data = word.charAt(0);
node.isWord = false;
dictionary.put(word.charAt(0), node);
}
int i = 1;
while(i < len) {
char ch = word.charAt(i);
if(ch < node.data) {
NodeW<Character> child = new NodeW<>();
if(!node.previous.containsKey(ch)) {
node.previous.put(ch, child);
child.data = ch;
}
else
child = node.previous.get(ch);
if(i == len-1) {
child.isWord = true;
count++;
}
node = child;
} else if(ch > node.data) {
NodeW<Character> child = new NodeW<>();
if(!node.next.containsKey(ch)) {
node.next.put(ch, child);
child.data = ch;
}
else
child = node.next.get(ch);
if(i == len-1) {
child.isWord = true;
count++;
}
else
child.isWord = false;
node = child;
} else if(ch == node.data) {
NodeW<Character> eq = new NodeW<>();
node.eq = eq;
eq.data = ch;
if(i == len-1)
eq.isWord = true;
node = eq;
}
i++;
}
});
}
/**
* Constructor which will initialize the static variables assuming the characters will
* be from a to z
*/
public Dictionary() {
positions = new HashMap<>();
characters = new ArrayList<>();
positions.put('a', 0);
positions.put('b', 1);
positions.put('c', 2);
positions.put('d', 3);
positions.put('e', 4);
positions.put('f', 5);
positions.put('g', 6);
positions.put('h', 7);
positions.put('i', 8);
positions.put('j', 9);
positions.put('k', 10);
positions.put('l', 11);
positions.put('m', 12);
positions.put('n', 13);
positions.put('o', 14);
positions.put('p', 15);
positions.put('q', 16);
positions.put('r', 17);
positions.put('s', 18);
positions.put('t', 19);
positions.put('u', 20);
positions.put('v', 21);
positions.put('w', 22);
positions.put('x', 23);
positions.put('y', 24);
positions.put('z', 25);
characters.add('a');
characters.add('b');
characters.add('c');
characters.add('d');
characters.add('e');
characters.add('f');
characters.add('g');
characters.add('h');
characters.add('i');
characters.add('j');
characters.add('k');
characters.add('l');
characters.add('m');
characters.add('n');
characters.add('o');
characters.add('p');
characters.add('q');
characters.add('r');
characters.add('s');
characters.add('t');
characters.add('u');
characters.add('a');
characters.add('v');
characters.add('w');
characters.add('x');
characters.add('y');
characters.add('z');
dictionary = new HashMap<>();
}
}
class NodeW<T> {
public T data;
public HashMap<T, NodeW<T>> previous;
public HashMap<T, NodeW<T>> next;
public NodeW<T> eq;
public boolean isWord = false;
public NodeW() {
previous = new HashMap<>();
next = new HashMap<>();
}
}
These seem to be find if having certain kind of words but I don't feel that these will be fine to develop dictionary as we will need to customize it. So I just thought to try these using Tree, Node & HashMap, as shown below. Though it may not be working extensively but I think, it can be used to further enhance this approach to cover other scenarios. Will be happy to know your views.
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
public class Dictionary {
private static HashMap<Character, Integer> positions;
private static ArrayList<Character> characters;
private static HashMap<Character, NodeW<Character>> dictionary;
private static int count;
public static void main(String[] args) {
new Dictionary();
ArrayList<String> words = new ArrayList<>();
words.add("abc");
words.add("bdc");
words.add("bcadgh");
words.add("bca");
words.add("bcaagh");
words.add("bych");
words.add("cbaeft");
makeDictionary(words);
System.out.println("Number of distinct starting characters in dictionary : " + dictionary.size());
System.out.println("Is available? " +
isWord("bcadgh"));
ArrayList<String> results = new ArrayList<>();
wordStartingFrom('a', results);
System.out.println("Words starting from 'a' : ");
results.forEach(System.out::println);
System.out.println("Total number of words in dictionary : " + count);
}
/**
* Finds the words starting from the given character.
* @param ch
* @param results
*/
private static void wordStartingFrom(Character ch, ArrayList<String> results) {
NodeW<Character> node = dictionary.get(ch);
StringBuilder sb = new StringBuilder();
if(node != null) {
sb.append(ch);
List<NodeW<Character>> list = getOrderedNext(node);
for(NodeW<Character> child : list) {
if(child != null)
sb.append(child.data);
if(child != null && child.isWord)
results.add(sb.toString());
node = child;
wordHavingChar(node, results, sb);
sb = new StringBuilder();
sb.append(ch);
}
node = null;
}
}
/**
* Finds the words starting from the given node.
* @param node
* @param results
* @param sb
*/
private static void wordHavingChar(NodeW<Character> node, ArrayList<String> results, StringBuilder sb) {
while(node != null) {
List<NodeW<Character>> list = getOrderedNext(node);
if(list.isEmpty())
node = null;
for(NodeW<Character> child : list) {
StringBuilder sb1 = new StringBuilder();
sb1.append(sb);
if(child != null)
sb.append(child.data);
if(child != null && child.isWord)
results.add(sb.toString());
node = child;
wordHavingChar(node, results, sb);
sb = sb1;
}
node = null;
}
}
/**
* Gets the sorted list of nodes next to the given node in the dictionary.
* @param node
* @return
*/
private static List<NodeW<Character>> getOrderedNext(NodeW<Character> node) {
List<NodeW<Character>> results = new ArrayList<>();
Character chars = node.data;
int pos = positions.get(chars);
List<Character> before = characters.subList(0, pos+1);
for(Character ch : before) {
if(node.previous.containsKey(ch))
results.add(node.previous.get(ch));
else if(node.eq != null && node.eq.data == ch)
results.add(node.eq);
}
List<Character> after = characters.subList(pos+1, 26);
for(Character ch : after) {
if(node.next.containsKey(ch))
results.add(node.next.get(ch));
}
return results;
}
/**
* Checks if the given word exists in the dictionary.
* @param word
* @return
*/
private static boolean isWord(String word) {
int len = word.length();
int i = 1;
NodeW<Character> node = dictionary.get(word.charAt(0));
while(i < len && node != null) {
node = getNextNode(word.charAt(i), node);
if(i == len-1 && node != null && node.isWord)
return true;
i++;
}
return false;
}
/**
* Gets the next node containing the given character, else null is returned.
* @param ch
* @param node
* @return
*/
private static NodeW<Character> getNextNode(Character ch, NodeW<Character> node) {
if(node.data == ch)
return node.eq;
else if(node.data > ch)
return node.previous.get(ch);
else
return node.next.get(ch);
}
/**
* Creates the dictionary in memory from the given list of words.
* @param words
*/
private static void makeDictionary(ArrayList<String> words) {
words.forEach( word -> {
int len = word.length();
NodeW<Character> node = dictionary.get(word.charAt(0));
if(node == null) {
node = new NodeW<>();
node.data = word.charAt(0);
node.isWord = false;
dictionary.put(word.charAt(0), node);
}
int i = 1;
while(i < len) {
char ch = word.charAt(i);
if(ch < node.data) {
NodeW<Character> child = new NodeW<>();
if(!node.previous.containsKey(ch)) {
node.previous.put(ch, child);
child.data = ch;
}
else
child = node.previous.get(ch);
if(i == len-1) {
child.isWord = true;
count++;
}
node = child;
} else if(ch > node.data) {
NodeW<Character> child = new NodeW<>();
if(!node.next.containsKey(ch)) {
node.next.put(ch, child);
child.data = ch;
}
else
child = node.next.get(ch);
if(i == len-1) {
child.isWord = true;
count++;
}
else
child.isWord = false;
node = child;
} else if(ch == node.data) {
NodeW<Character> eq = new NodeW<>();
node.eq = eq;
eq.data = ch;
if(i == len-1)
eq.isWord = true;
node = eq;
}
i++;
}
});
}
/**
* Constructor which will initialize the static variables assuming the characters will
* be from a to z
*/
public Dictionary() {
positions = new HashMap<>();
characters = new ArrayList<>();
positions.put('a', 0);
positions.put('b', 1);
positions.put('c', 2);
positions.put('d', 3);
positions.put('e', 4);
positions.put('f', 5);
positions.put('g', 6);
positions.put('h', 7);
positions.put('i', 8);
positions.put('j', 9);
positions.put('k', 10);
positions.put('l', 11);
positions.put('m', 12);
positions.put('n', 13);
positions.put('o', 14);
positions.put('p', 15);
positions.put('q', 16);
positions.put('r', 17);
positions.put('s', 18);
positions.put('t', 19);
positions.put('u', 20);
positions.put('v', 21);
positions.put('w', 22);
positions.put('x', 23);
positions.put('y', 24);
positions.put('z', 25);
characters.add('a');
characters.add('b');
characters.add('c');
characters.add('d');
characters.add('e');
characters.add('f');
characters.add('g');
characters.add('h');
characters.add('i');
characters.add('j');
characters.add('k');
characters.add('l');
characters.add('m');
characters.add('n');
characters.add('o');
characters.add('p');
characters.add('q');
characters.add('r');
characters.add('s');
characters.add('t');
characters.add('u');
characters.add('a');
characters.add('v');
characters.add('w');
characters.add('x');
characters.add('y');
characters.add('z');
dictionary = new HashMap<>();
}
}
class NodeW<T> {
public T data;
public HashMap<T, NodeW<T>> previous;
public HashMap<T, NodeW<T>> next;
public NodeW<T> eq;
public boolean isWord = false;
public NodeW() {
previous = new HashMap<>();
next = new HashMap<>();
}
}
