A trie implementation in Java with the following features:

• finds words that start with the given prefix;

• finds all words occurring in a given pattern from left to right;

  e.g: given the pattern "wverticall" the words found will be "vertical", "call" and "all";

• finds all the valid words from the permutation of the given letters;

  e.g: given the letters "a e r d" the words found will be "dare","dear","are","rad","red","read","ear" and "era";

• finds all the words that fit in the given string expression according to the wildcards' position;

  e.g: given the expression "s??ce", where the symbol ? is the wildcard, the words found will be "slice", "space", "since", ecc ...

Useful for finding anagrams and words.

A faster and lighter implementation is given by this DoubleArrayTrie

Create and populate the Trie

Trie trie = new Trie();
for(String word : myDictionary) {
  trie.insert(word);
}

Only for the match method you need to call first the buildSuffixLinks method

trie.buildSuffixLinks();
ArrayList<String> words = trie.match("wverticall");

• Improve performance of permute and query methods by making them from recursive to iterative
• Write own writeObject and readObject methods to speed up serialization and reduce the risk of StackOverflow