How does the Java spell checker work?
This little program was written for an assignment in a data structures and algorithms class. I'll just note the basic requirements:
Given an inputted string, the program should check to see if it exists in a dictionary of correctly spelled words. If not, it should return a list of words that are obtainable by:
adding any character to the beginning or end of the inputted string
removing any single character from the inputted string
swapping any two adjacent characters in the string
The primary data structure is embodied in the Dictionary class, which is my implementation of a separately-chaining hash list, and the important algorithms are found in the charAppended(), charMissing() and charsSwapped() methods.
Everything works as expected - I'm just looking for tips about anything that can be done more cleanly, efficiently or better aligned with best practices.
General
Many of the variable names lack meaning and are inconsistent. I cover some of them specifically below, but for example print is not a good choice for a list of suggestions--even though you intend to print them. Instead, suggestions clearly identify what the list holds.
Learn to use JavaDoc for documenting public classes and methods. Not only is it nicer to read than one-liners, developing this habit early will demonstrate your goal to become a professional engineer (if that's the case).
/**
* Add the key to this dictionary if not already present.
*
* @param key hash determines the bucket to receive it
*/
public void add(String key) { ... }
/**
* Determines if the key is present in this dictionary.
*
* @param key hash determines the bucket to search
* @return true if key is present
*/public boolean contains(String input) { ... }
Java Spell Checker
You make a good effort at breaking up the methods and separating concerns, but I would take it a step further. The methods that build alternate spellings should not be responsible for checking the dictionary. Instead, combine all misspellings into a single list and search the dictionary in one place. This also allows you to remove duplicates and avoid wasted lookups.
I would also completely separate all output, possibly to a new UI class to allow reuse. You did pretty well here, but printSuggestions should receive the list of suggestions instead of calling makeSuggestions itself.
private void printStatusAndSuggestions(String input) {
System.out.println();
System.out.print(input);
if (dict.contains(input) {
System.out.println(" is spelled correctly.");
} else {
System.out.print(" is not spelled correctly,");
printSuggestions(suggest(input));
}
}
private void printSuggestions(Set suggestions) {
if (suggestions.isEmpty()) {
System.out.println(" and I have no idea what word you could mean."
} else {
... print them ...
}
}
private Set suggest(String input) {
Set suggestions = new HashSet<>();
Set alternates = makeAlternates(input);
for (String alternate : alternates) {
if (dict.contains(alternate) {
suggestions.add(alternate);
}
}
return suggestions;
}If Dictionary implemented the Set interface, you could use the built-in intersection method to do the lookups for you.
private Set suggest(String input) {
return makeAlternates(input).retainAll(dict);
}input.equals("") is better expressed as input.isEmpty(). You may want to trim the input to remove leading/trailing spaces: input = scan.nextLine().trim();
This applies similarly to ArrayList: print.isEmpty() instead of print.size() == 0.
pricing Suggestions creates a StringBuilder needlessly when there are no suggestions.
You use two different methods of concatenating strings when building suggestions: an implicit StringBuilder and String.concat. Both are fine in different circumstances (though I confess that I've never used the latter), but make sure you combine all the concatenations in one statement. Breaking them across statements uses a new builder for each statement. charsSwapped is especially egregious requiring three for each suggestion instead of one.
String working = input.substring(0, i)
+ input.charAt(i + 1);
+ input.charAt(i);
+ input.substring(i + 2);Dictionary
Turn M into a constant. As it stands, you're initialising the field to 1319 and then reassigning it to itself in the constructor. Perhaps BUCKET_COUNT is a better name.
Alternatively, add a constructor that takes the value as a parameter. While we're at it, how about buckets in place of the very generic name array? It's rarely a good idea to name a primitive variable based solely on its type.
public static final int DEFAULT_BUCKET_COUNT = 1319;
private final bucketCount;
private final Bucket[] buckets;
public Dictionary() {
this(DEFAULT_BUCKET_COUNT);
}
public Dictionary(int bucketCount) {
this.bucketCount = bucketCount;
... create empty buckets ...
}Bucket/Node
Both of these can be static since they don't access the outer classes' members.
You don't really need Bucket and may consider rewriting the code to remove it to see the difference. It's not a huge improvement but may simplify the code.
As with Dictionaries, add and contain make more sense than put and get.
Be consistent with naming across methods. In Bucket, get takes in while put takes key, but in and key represent the same things and as such should use the same name: key. Also, stick with curr to avoid confusion with Node.next.
@Czippers nailed this one: get and put should use the same looping construct since they're both walking the list in order and possibly stopping at some point.