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
andquery
methods by making them from recursive to iterative - Write own writeObject and readObject methods to speed up serialization and reduce the risk of
StackOverflow