Design a method to find the frequency of occurrences of any given word in a book.
My initial thoughts:
Assume this query would be asked for multiple times. Otherwise, if it’s a one-time thing, we can do no better than scanning through the book. We then need to build a Trie with nodes as character along with its count. When asked for particular word, we search through the tree.
My initial codes:
public class Node { private char c; private int count = 1; private List<Node> children = new LinkedList<Node>(); public Node() { } public Node(char c) { this.c = c; } public char getC() { return c; } public void setC(char c) { this.c = c; } public int getCount() { return count; } public void setCount(int count) { this.count = count; } public void increaseCount() { this.count++; } public List<Node> getChildren() { return children; } public Node addChild(char c) { for (Node node : children) { if (node.getC() == c) { node.increaseCount(); return node; } } Node child = new Node(c); this.children.add(child); return child; } public Node getChild(char c) { for (Node node : children) { if (node.getC() == c) { return node; } } return null; } @Override public String toString() { return "(" + c + ", " + count + ")"; } } private Node root = new Node(); public void buildTree(String[] book) { for (String word : book) { Node current = root; for (int i = 0; i < word.length(); ++i) { char c = word.charAt(i); current = current.addChild(c); } } } public int getFrequency(String word) { Node current = root; for (int i = 0; i < word.length(); ++i) { char c = word.charAt(i); current = current.getChild(c); if (current == null) return 0; } return current.getCount(); }Solution:
Hashtable<String, Integer> setupDictionary(String[] book) { Hashtable<String, Integer> table = new Hashtable<String, Integer>(); for (String word : book) { word = word.toLowerCase(); if (word.trim() != "") { if (!table.containsKey(word)) table.put(word, 0); table.put(word, table.get(word) + 1); } } return table; } int getFrequency(Hashtable<String, Integer> table, String word) { if (table == null || word == null) return -1; word = word.toLowerCase(); if (table.containsKey(word)) { return table.get(word); } return 0; }Comments: Error conditions:
- Trim and toUpperCase the word before inserting into hashtable.
- Error condition for table==null and/or query==null.
- toUpperCase the query before searching through hashtable.