public class Trie
{
private class TrieNode
{
public TrieNode[] children;
public ArrayList<String> words;
public TrieNode()
{
children = new TrieNode[26];
words = new ArrayList<String>();
}
}
private TrieNode root;
public Trie(String file)
{
root = new TrieNode();
BufferedReader in = new BufferedReader(new FileReader(file));
String str;
while ((str = in.readLine()) != null)
{
char[] chars = str.toCharArray();
Arrays.sort(chars);
insert(root, chars, 0);
}
in.close();
}
private void insert(TrieNode node, char[] chars, int x)
{
if (x >= chars.length)
{
node.words.add(new String(chars));
return;
}
if(node.children[chars[x]-'a'] == null)
node.children[chars[x]-'a'] = new TrieNode();
insert(node.children[chars[x]-'a'], chars, x+1);
}
public ArrayList<String> getPermutations(String s)
{
char[] chars = s.toCharArray();
Arrays.sort(chars);
TrieNode current = root;
for (int i=0; i < chars.length && current != null; i++)
current = current.children[chars[i]-'a']
return (current == null) ? new ArrayList<String>() : current.words.clone();
}
}
public static void main(String[] args)
{
Trie dict = new Trie("c://scrabbledictionary.txt");
ArrayList<String> words = dict.getPermutations("infantry");
}