This week only. Pastebin PRO Accounts Christmas Special! Don't miss out!Want more features on Pastebin? Sign Up, it's FREE!
Guest

Trie

By: a guest on Feb 9th, 2012  |  syntax: Java  |  size: 1.44 KB  |  views: 283  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. public class Trie
  2. {
  3.   private class TrieNode
  4.   {
  5.     public TrieNode[] children;
  6.     public ArrayList<String> words;
  7.  
  8.     public TrieNode()
  9.     {
  10.       children = new TrieNode[26];
  11.       words = new ArrayList<String>();
  12.     }
  13.   }
  14.  
  15.   private TrieNode root;
  16.  
  17.   public Trie(String file)
  18.   {
  19.     root = new TrieNode();
  20.    
  21.     BufferedReader in = new BufferedReader(new FileReader(file));
  22.     String str;
  23.     while ((str = in.readLine()) != null)
  24.     {
  25.       char[] chars = str.toCharArray();
  26.       Arrays.sort(chars);
  27.       insert(root, chars, 0);
  28.     }
  29.     in.close();
  30.   }
  31.  
  32.   private void insert(TrieNode node, char[] chars, int x)
  33.   {    
  34.     if (x >= chars.length)
  35.     {
  36.       node.words.add(new String(chars));
  37.       return;
  38.     }
  39.    
  40.     if(node.children[chars[x]-'a'] == null)
  41.       node.children[chars[x]-'a'] = new TrieNode();
  42.    
  43.     insert(node.children[chars[x]-'a'], chars, x+1);
  44.   }
  45.  
  46.   public ArrayList<String> getPermutations(String s)
  47.   {
  48.     char[] chars = s.toCharArray();
  49.     Arrays.sort(chars);
  50.    
  51.     TrieNode current = root;
  52.     for (int i=0; i < chars.length && current != null; i++)
  53.       current = current.children[chars[i]-'a']
  54.    
  55.     return (current == null) ? new ArrayList<String>() : current.words.clone();
  56.   }
  57. }
  58.  
  59. public static void main(String[] args)
  60. {
  61.   Trie dict = new Trie("c://scrabbledictionary.txt");
  62.   ArrayList<String> words = dict.getPermutations("infantry");
  63. }
clone this paste RAW Paste Data