patternjavaMinor
A Trie data structure in Java
Viewed 0 times
javadatastructuretrie
Problem
this is the first time I' implementing a Trie. My goal was to make it as simple as possible. So here is the result:
Can I simplify anything else? Are there some things I can change to increase performance ? Also any feedback on code quality/design is welcome :)
Node.java
Trie.java
Can I simplify anything else? Are there some things I can change to increase performance ? Also any feedback on code quality/design is welcome :)
Node.java
package trie;
public class Node {
final Node[] children = new Node[26];
boolean isEnd = false;
}Trie.java
package trie;
import java.util.ArrayList;
import java.util.List;
public class Trie {
static final int ALPHABET_SIZE = 26;
final Node root = new Node();
void add(String str) {
Node curr = root;
for (int i = 0; i prefixedWords(String str) {
Node curr = getNode(str);
List prefixedWords = new ArrayList<>();
DFS(curr, str, prefixedWords);
return prefixedWords;
}
void DFS(Node root, String prefix, List list) {
if (root != null) {
if (root.isEnd) {
list.add(prefix);
}
for (int i = 0; i < ALPHABET_SIZE; i++) {
if (root.children[i] != null) {
DFS(root.children[i], prefix + (char) (i + 'a'), list);
}
}
}
}
}Solution
Magic numbers
Consider changing this to
Now you don't have to manually change the array size if you change the alphabet size. It may not matter here (we are unlikely to add a letter to the alphabet and you may not need to change alphabets), but it is good practice to set things up so that the system makes them the same.
Range-based
This could be
Then you don't have to maintain
You also may want to check that
Early exit
This could be
This way you don't have to enclose the entire method inside an
The method should be
Performance
I don't see anything that leaps out at me performance wise. Tries are best at prefix searches and relatively slow and memory intensive to build. For many uses, a
Anyway, time your actual usage to see if this solution is faster than other solutions.
final Node[] children = new Node[26];Consider changing this to
final Node[] children = new Node[Trie.ALPHABET_SIZE];Now you don't have to manually change the array size if you change the alphabet size. It may not matter here (we are unlikely to add a letter to the alphabet and you may not need to change alphabets), but it is good practice to set things up so that the system makes them the same.
Range-based
for loopsfor (int i = 0; i < str.length(); i++) {
int idx = str.charAt(i) - 'a';This could be
for (char c : str.toCharArray()) {
int idx = c - 'a';Then you don't have to maintain
i manually. You also may want to check that
idx is in the range 0 to 25. You currently just trust that that will be so. Early exit
void DFS(Node root, String prefix, List list) {
if (root != null) {This could be
static void DFS(Node root, String prefix, List list) {
if (root == null) {
return;
}This way you don't have to enclose the entire method inside an
if. You can just bail out immediately. The method should be
static because it doesn't use any of the state of the trie. In fact, one of its parameters has the same name as an object field. Performance
I don't see anything that leaps out at me performance wise. Tries are best at prefix searches and relatively slow and memory intensive to build. For many uses, a
HashSet (for full word searches) or even an ArrayList is faster. We need a long run to amortize out the build time enough to give faster prefix lookups. Anyway, time your actual usage to see if this solution is faster than other solutions.
Code Snippets
final Node[] children = new Node[26];final Node[] children = new Node[Trie.ALPHABET_SIZE];for (int i = 0; i < str.length(); i++) {
int idx = str.charAt(i) - 'a';for (char c : str.toCharArray()) {
int idx = c - 'a';void DFS(Node root, String prefix, List<String> list) {
if (root != null) {Context
StackExchange Code Review Q#161035, answer score: 2
Revisions (0)
No revisions yet.