Bard College – Computer Science – Data Structures
Spell Checker: Two Ways
Our first program acts as a spell checker. It checks if a candidate word exists in a dictionary file named words — this file typically lives in /usr/share/dict/words on Unix systems, but is also posted on Moodle.
publicstaticboolean bcheck(String query, int low, int high){
returnfalse;
}
publicstaticvoid main(String[] args){
loadWords();
if (args.length > 0) testWords = args;
for (String word: testWords){
if (check(word)){
StdOut.println("found " + word);
}
else{
StdOut.println(word + " not found");
}
}
}
}
Complete this class by writing methods that spell-check the candidate word; you will write two versions of this method: one that uses simple linear search(lcheck) and another that uses recursive binary search(bcheck).
Convert the book’s iterative version of binary search(that uses a while loop) to a recursive variety.
How much better is the binary search version than the linear method?
Jumble: Two Ways
Word jumbles, also known as anagrams, are a fun word game found in many newspapers.
First Try
Translate the following Python anagram solver into Java and find the four jumbled words in the previous puzzle(can solve the final riddle?).
Spell Checker: Two Ways
import edu.princeton.cs.algs4.*;
public class SpellCheck{ private static String[] words; private static String[] testWords = {"bear", "jackalope", "liger", "zebra"};
public static void loadWords(){ words = In.readStrings("words"); }
public static boolean check(String query){ return lcheck(query); // or bcheck } public static boolean lcheck(String query){ return false; } public static boolean bcheck(String query, int low, int high){ return false; } public static void main(String[] args){ loadWords(); if (args.length > 0) testWords = args; for (String word: testWords){ if (check(word)){ StdOut.println("found " + word); } else{ StdOut.println(word + " not found"); } } }}Jumble: Two Ways
First Try