title: Implement T9 Dictionary using Trie?
body: <p>I have to implement the T9 Dictionary .</p>
  
  <p>Essentially, when I am pressing any of the 9 keys, it should show me
  the top 5 words that can be started with that combination of keys.</p>
  
  <p>If I type '46', it can give 'hotel' or 'good' depending on whether I
  intended 'g' or 'h' when I pressed 4.</p>
  
  <p>The priority is based on which words are relatively popular - you can
  use, say, the first 5000 words from the top <a href="http://www.dict.org/100kfound.txt.gz" rel="nofollow">100 000</a> words.</p>
  
  <p>The code I am doing is:</p>
  
  <p><strong>Import</strong></p>
  
  <pre><code>import java.io.BufferedReader;
  import java.io.File;
  import java.io.FileReader;
  import java.util.Date;
  import java.util.HashMap;
  import java.util.LinkedList;
  import java.util.List;
  import java.util.Map;
  </code></pre>
  
  <p><strong>T9Dict class</strong></p>
  
  <pre><code>public class T9Dict {
  
      private static final Runtime s_runtime = Runtime.getRuntime();
  
      public static void main(String[] args) throws Exception {
  
          runGC();
          long heap1 = usedMemory();
  
          long start = new Date().getTime();
          Trie trie = Trie.getInstance();
          System.out.println("Creating Dictionary");
          File f = new File("C:\\Users\\hp1\\Desktop\\100kfound.txt");
          BufferedReader br = new BufferedReader(new FileReader(f));
          String s = br.readLine();
          int i = 0;
          do {
              i++;
              trie.add(s);
              s = br.readLine();
          } while (s != null);
          br.close();
          long end = new Date().getTime();
          long time = (end - start);
          System.out.println("Loaded Dictionary with " + i + " words in " + time
                  + " msec");
  
          // runGC();
          long heap2 = usedMemory(); // take an "after" heap snapshot:
          System.out.println("Memory used = " + (heap2 - heap1));
  
          String pattern = "4663";
          start = new Date().getTime();
          String word = trie.getWord(pattern);
          end = new Date().getTime();
          time = (end - start);
          System.out.println("Found word : " + word + " in " + time + " msec");
  
      }
  
      private static void runGC() throws Exception {
          // for whatever reason it helps to call Runtime.gc()
          // using several method calls:
          for (int r = 0; r &lt; 4; ++r) {
              _runGC();
          }
      }
  
      private static void _runGC() throws Exception {
          long usedMem1 = usedMemory();
          long usedMem2 = Long.MAX_VALUE;
  
          for (int i = 0; (usedMem1 &lt; usedMem2) &amp;&amp; (i &lt; 1000); ++i) {
              s_runtime.runFinalization();
              s_runtime.gc();
              Thread.currentThread().yield();
  
              usedMem2 = usedMem1;
              usedMem1 = usedMemory();
          }
      }
  
      private static long usedMemory() {
          return s_runtime.totalMemory() - s_runtime.freeMemory();
      }
  }
  </code></pre>
  
  <p><strong>Trie class</strong></p>
  
  <pre><code>class Trie {
  
      private static final String regex = "[a-zA-Z]*";
      private static Trie instance = null;
      Node root = null;
      Map&lt;Character, Integer&gt; map = new HashMap&lt;Character, Integer&gt;();
  
      private Trie() {
          map.put('a', 2);
          map.put('b', 2);
          map.put('c', 2);
          map.put('d', 3);
          map.put('e', 3);
          map.put('f', 3);
          map.put('g', 4);
          map.put('h', 4);
          map.put('i', 4);
          map.put('j', 5);
          map.put('k', 5);
          map.put('l', 5);
          map.put('m', 6);
          map.put('n', 6);
          map.put('o', 6);
          map.put('p', 7);
          map.put('q', 7);
          map.put('r', 7);
          map.put('s', 7);
          map.put('t', 8);
          map.put('u', 8);
          map.put('v', 8);
          map.put('w', 9);
          map.put('x', 9);
          map.put('y', 9);
          map.put('z', 9);
      }
  
      private int getVal(char c) {
          return map.get(c);
      }
  
      public static Trie getInstance() {
          if (instance == null) {
              synchronized (Trie.class) {
                  instance = new Trie();
              }
          }
          return instance;
      }
  
      public String getWord(String pattern) {
          String s = null;
          Node node = root;
          int i = 0;
          int num = 0;
          while (i &lt; pattern.length()) {
              num = pattern.charAt(i) - '0';
              if (num == node.val) {
                  i++;
                  if (i == pattern.length()) {
                      s = node.list.get(0);
                  }
                  node = node.middle;
              } else if (num &lt; node.val) {
                  if (i == pattern.length()) {
                      s = node.list.get(0);
                  }
                  node = node.left;
              } else {
                  if (i == pattern.length()) {
                      s = node.list.get(0);
                  }
                  node = node.right;
              }
  
          }
          return s;
      }
  
      public void add(String s) {
  
          if (s.length() &gt; 0) {
              s = s.toLowerCase();
              System.out.println("Adding : " + s);
              if (root == null) {
                  root = new Node(this.getVal(s.charAt(0)));
                  Node node = root;
                  Node temp = null;
                  for (int i = 1; i &lt; s.length(); i++) {
                      temp = new Node(getVal(s.charAt(i)));
                      node.middle = temp;
                      node = temp;
                      if (i == s.length() - 1) {
                          temp.set(s);
                      }
                  }
              } else {
                  Node node = root;
                  int i = 0;
                  Node temp = null;
                  int val = 0;
                  while (i &lt; s.length()) {
                      val = getVal(s.charAt(i));
                      if (node.val == val) {
                          if (i == s.length() - 1) {
                              node.set(s);
                              i++;
                          } else {
                              i++;
                              if (node.middle == null) {
                                  while (i &lt; s.length()) {
                                      val = getVal(s.charAt(i));
                                      temp = new Node(val);
                                      node.middle = temp;
                                      node = temp;
                                      if (i == s.length() - 1) {
                                          temp.set(s);
                                      }
                                      i++;
                                  }
                              } else {
                                  node = node.middle;
                              }
                          }
                      } else if (val &lt; node.val) {
                          if (node.left == null) {
                              temp = new Node(val);
                              node.left = temp;
                              node = temp;
                              if (i == s.length() - 1) {
                                  temp.set(s);
                              } else {
                                  i++;
                                  while (i &lt; s.length()) {
                                      val = getVal(s.charAt(i));
                                      temp = new Node(val);
                                      node.middle = temp;
                                      node = temp;
                                      if (i == s.length() - 1) {
                                          temp.set(s);
                                      }
                                      i++;
                                  }
                              }
  
                          } else {
                              node = node.left;
                          }
                      } else {
                          if (node.right == null) {
                              temp = new Node(val);
                              node.right = temp;
                              node = temp;
                              if (i == s.length() - 1) {
                                  temp.set(s);
                              } else {
                                  i++;
                                  while (i &lt; s.length()) {
                                      val = getVal(s.charAt(i));
                                      temp = new Node(val);
                                      node.middle = temp;
                                      node = temp;
                                      if (i == s.length() - 1) {
                                          temp.set(s);
                                      }
                                      i++;
                                  }
                              }
                          } else {
                              node = node.right;
                          }
                      }
                  }
              }
          }
      }
  }
  </code></pre>
  
  <p><strong>Node class</strong></p>
  
  <pre><code>class Node {
  
      int val;
      Node left;
      Node middle;
      Node right;
      List&lt;String&gt; list = new LinkedList&lt;String&gt;();
  
      public Node(int val) {
          this.val = val;
      }
  
      public void set(String s) {
          list.add(s);
      }
  
      public String toString() {
          return String.valueOf(val);
      }
  }
  </code></pre>
  
  <p>This code is giving nullpointerexception when adding to Trie
  I cannot find the solution please help</p>