Advertisement
shashi_k_

Trie based dictionary

Feb 5th, 2015
641
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 2.90 KB | None | 0 0
  1. /**
  2.  *
  3.  */
  4. package com.kant.amazon;
  5.  
  6. import java.util.ArrayList;
  7. import java.util.Arrays;
  8. import java.util.List;
  9.  
  10. /**
  11.  * @author shashi
  12.  *
  13.  */
  14. public class TrieBasedDictionary {
  15.  
  16.     TrieNode root;
  17.  
  18.     public TrieBasedDictionary() {
  19.         root = new TrieNode();
  20.     }
  21.  
  22.     /**
  23.      *
  24.      * @param items
  25.      */
  26.     public void addWordsFromList(List<String> items) {
  27.         for (String item : items) {
  28.             String[] keyVal = item.split(":");
  29.             root.addWord(keyVal[0], keyVal[1]);
  30.         }
  31.     }
  32.  
  33.     public String findWordMeaning(String text) {
  34.         return root.findWordMeaning(text.toUpperCase());
  35.     }
  36.  
  37.     /**
  38.      *
  39.      * @param text
  40.      * @return
  41.      */
  42.     public boolean hasPrefix(String text) {
  43.         return root.isValidPrefix(text);
  44.     }
  45.  
  46.     /**
  47.      *
  48.      * @param args
  49.      */
  50.     public static void main(String[] args) {
  51.         TrieBasedDictionary dictionary = new TrieBasedDictionary();
  52.         List<String> words = new ArrayList<>();
  53.         words.add("AGNOSTIC:someone who believes that it is impossible to know whether there is a God or not.");
  54.         words.add("ALOOF:being distant in manner or feeling, unsympathetic");
  55.         words.add("BONA FIDE:a gesture made in good faith ");
  56.         words.add("CAVEAT:a warning or caution given");
  57.         words.add("DESPICABLE:deserving of contempt");
  58.  
  59.         dictionary.addWordsFromList(words);
  60.         System.out.println(dictionary.hasPrefix("BONA "));
  61.         System.out.println(dictionary.findWordMeaning("BONA FIDE"));
  62.     }
  63.  
  64. }
  65.  
  66. /**
  67.  *
  68.  * @author shashi
  69.  *
  70.  */
  71. class TrieNode {
  72.     TrieNode[] children;
  73.     boolean isAWord;
  74.     int countPrefixes; // number of prefixes has this node.
  75.     String meaning; // meaning of word
  76.  
  77.     public TrieNode() {
  78.         countPrefixes = 0;
  79.         isAWord = false;
  80.         children = new TrieNode[255];
  81.         Arrays.fill(children, null);
  82.         meaning = null;
  83.     }
  84.  
  85.     /**
  86.      *
  87.      * @param input
  88.      * @param meaning
  89.      */
  90.     public void addWord(String input, String meaning) {
  91.         if (input.isEmpty()) {
  92.             this.meaning = meaning;
  93.             this.isAWord = true;
  94.             return;
  95.         }
  96.         countPrefixes++;
  97.         int first = input.charAt(0);
  98.         if (children[first] == null) {
  99.             children[first] = new TrieNode();
  100.         }
  101.         children[first].addWord(input.substring(1), meaning);
  102.     }
  103.  
  104.     /**
  105.      *
  106.      * @param key
  107.      * @return
  108.      */
  109.     public String findWordMeaning(String key) {
  110.         if (key != null) {
  111.             if (key.isEmpty()) {
  112.                 if (isAWord) {
  113.                     return meaning;
  114.                 }
  115.                 System.out.println("word not found");
  116.                 return null;
  117.             }
  118.             int first = key.charAt(0);
  119.             if (children[first] != null) {
  120.                 return children[first].findWordMeaning(key.substring(1));
  121.             }
  122.         }
  123.         return null;
  124.     }
  125.  
  126.     /**
  127.      *
  128.      * @param text
  129.      * @return
  130.      */
  131.     public boolean isValidPrefix(String text) {
  132.         if (text != null) {
  133.             if (text.isEmpty())
  134.                 return true;
  135.             int first = text.charAt(0);
  136.             if (children[first] != null) {
  137.                 if (text.length() == 1) {
  138.                     return true;
  139.                 }
  140.                 return children[first].isValidPrefix(text.substring(1));
  141.             }
  142.         }
  143.         return false;
  144.     }
  145. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement