Lab 6: Word Games
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. 

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");
            }
        }
    }
}
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?).