Some thoughts:
- Your use of the default access level is probably incorrect. Public, private, and sometimes protected make much more sense. In particular, if this class is not to be used outside of its package, you can make the whole class default scope and let the methods be public. If it is to be used outside its package, everything should be public.
- In java, all variables should start with a lowercase letter except constants. You should also try to pick more descriptive names. There's no real cost to spelling out what a variable holds.
- Your use of comments is not ideal. Most of what you have should either belong to the the javadoc for the relevant method or it should be obvious based on a better variable name.
- You're not using standard java brace locations. They belong on the same line.
.isWord==true should just be .isWord. You don't need to compare boolean variables to true or false.- Helper methods would clean up your API by not forcing clients to pass in the node,
0 and "" with every call.
- It would be a better separation of concerns if your
Dict class only found the words and didn't output them. Let the caller handle that part. It greatly increases the reusability of the class.
- This may be a bug -
insertWord() is always returning the same node that was passed in. Why bother?
- The
add prefix is more commonly used in the standard API than insert. I would rename insertWord() to addWord().
Putting it all together, if I were writing this class, it would look more like this.
import java.util.ArrayList;
import java.util.List;
public final class Dict {
private static final int ALPHABET_SIZE = 26;
private static final int LOWERCASE_A_ASCII_VALUE = 97;
private boolean isWord;
private final Dict children[] = new Dict[ALPHABET_SIZE];
public Dict() {
super();
}
public void addWord(final String word) {
this.addWord(this, word.toCharArray(), 0);
}
private void addWord(final Dict node, final char[] letters, final int currentLetterIndex) {
if (currentLetterIndex == letters.length) {
node.isWord = true;
return;
}
final int linkno = indexForCharacter(letters[currentLetterIndex]);
if (node.children[linkno] == null) {
node.children[linkno] = new Dict();
}
this.addWord(node.children[linkno], letters, currentLetterIndex + 1);
}
public List<String> findWords() {
final List<String> words = new ArrayList<String>();
this.findWords(this, words, "");
return words;
}
private void findWords(final Dict node, final List<String> words, final String wordCandidate) {
for (int i = 0; i < ALPHABET_SIZE; i++) {
if (node.children[i] == null) {
continue;
}
if (node.children[i].isWord) {
words.add(wordCandidate + characterForIndex(i));
}
this.findWords(node.children[i], words, wordCandidate + characterForIndex(i));
}
}
private static int indexForCharacter(final char character) {
return character - LOWERCASE_A_ASCII_VALUE;
}
private static char characterForIndex(final int index) {
return (char) (index + LOWERCASE_A_ASCII_VALUE);
}
}
You could also use substring() with addWord() rather than passing the whole word and current index around. That's somewhat less efficient, but arguably cleaner to look at. If you wanted to go that route, the addWord() methods would look like
public void addWord(final String word) {
this.addWord(this, word);
}
private void addWord(final Dict node, final String remainingCharacters) {
if (remainingCharacters.isEmpty()) {
node.isWord = true;
return;
}
final int linkno = indexForCharacter(remainingCharacters.charAt(0));
if (node.children[linkno] == null) {
node.children[linkno] = new Dict();
}
this.addWord(node.children[linkno], remainingCharacters.substring(1));
}
Finally, the use of in-out variables (where a parameter has its contents modified by the method it gets passed into) is discouraged in public APIs. I did this with the findWords() method for a minor performance boost. It would be more correct but ever-so-slightly less performant to write them as follows. In hindsight, this is what should have been in the original proposal, with the more performant version as the "you might need to do ".
public List<String> findWords(final Dict node) {
return this.findWords(node, "");
}
private List<String> findWords(final Dict node, final String wordCandidate) {
final List<String> words = new ArrayList<String>();
for (int i = 0; i < ALPHABET_SIZE; i++) {
if (node.children[i] == null) {
continue;
}
if (node.children[i].isWord) {
words.add(wordCandidate + characterForIndex(i));
}
words.addAll(this.findWords(node.children[i], wordCandidate + characterForIndex(i)));
}
return words;
}
