Question

In this problem, we will use our knowledge of maps and lists to build a spell-checking program. The class Main contains the starter code for this problem; your task is to complete this program. You are provided with a file titled words.txt, which contains a list of valid English words, one per line. Your program should take as input a line of space-separated words representing a sentence. (No punctuation or capitalization will be used; all characters will be either the space character or a lowercase English letter). You should then output a list of words in the input that are misspelled, each on their own line, followed by a newline.

For example, if our input is:

teh qwick braown foxx jumpps ovar teh laizy dog

then we should print:

teh

qwick

braown

foxx

jumpps

ovar

teh

laizy

Restrictions:

(a) You may not use any of Java’s built-in data structures except for arrays. (In particular, you should write your own implementation of HashSet. I suggest calling this MyHashSet. Additionally, if you want to use lists to handle collisions, you will need to write your own implementation of a LinkedList or ArrayList.)

(b) Your algorithm should run in approximately O(m+n) time, where m is the total number of words in the file words.txt and n is the number of words in the input sentence.

(c) Violations of these restrictions will result in your receiving a zero for

this question

Hints :

(a) As a first step, I would recommend implementing your own ver-

sion of hash sets, called “MyHashSet”. I would suggest using the

MyLinkedList class from the last assignment as an example.

i. Your hash set should support an “add” method, which takes in

a string and puts it in the set.

ii. Your hash set should support a “contains” method, which takes

in a string and returns true if it’s in the set, and false otherwise.

iii. Your hash set should contain an array for holding the underlying

data.

iv. Your hash set should include a hash function. I suggest research-

ing one on the Internet and using that.

v. Your hash set should handle collisions somehow. I suggest using

a linked list.

(b) As a second step, you should iterate through the lines in

words.txt, and put each one in an instance of your hash set. Code for reading from the file has been provided; your job is to put each word in your

hash set.

(c) As a third step, you should iterate through the input words, check if

each one is in the set, and print it if it is not (i.e. it is not in the set

of real English words).

//Starter code

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.Scanner;

public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
  
// Step 1: load our txt file of English words.
try {
BufferedReader rd = new BufferedReader(new FileReader("words.txt"));
  
String currentLine = null;
while ((currentLine = rd.readLine()) != null) {
// TODO do something with the words we're reading
}
} catch (IOException e) {
System.out.println("Exception loading words.txt.");
}
  
// Step 2: read the sentence given into an array of strings
String[] sentenceWords;
String input = sc.nextLine();
if (input.equals("")) {
sentenceWords = new String[0];
} else {
sentenceWords = input.split(" ");
}
  
// Step 3: print all misspelled words
// TODO implement this using your own version of a HashSet.
}
}

Answer 1

// MyHashSet Implementation:

public class MyHashSet {

    private static class Entry {
        Object key;
        Entry next;
    }

    private Entry[] buckets;

    // size of the MyHashSet
    private int size;

    public MyHashSet(int capacity) {

        // each value is null initially, ie bucket[index] is null for all 0 < index < capacity
        buckets = new Entry[capacity];
        size = 0;
    }

    /**
     * Determines the index of buckets array where this hashCode will be mapped
     */
    private int hashFunction(int hashCode) {

        int index = hashCode;
        if (index < 0) {
            index = -index;
        }
        return index % buckets.length;
    }

    // Adds the specified element to this set if it is not already present
    public boolean add(String element) {

        int index = hashFunction(element.hashCode());
        Entry current = buckets[index];

        // Iterate to list to find if an entry already exists for this value of hashCode
        while (current != null) {
            // element is already in set
            if (current.key.equals(element)) {
                return false;
            }
            // otherwise visit next entry in the bucket
            current = current.next;
        }

        // no element found with that hashCode so add new entry
        Entry entry = new Entry();
        entry.key = element;
        // current Entry is null if bucket is empty
        // if it is not null it becomes next Entry
        entry.next = buckets[index];
        buckets[index] = entry;

        // increment size of MyHashSet
        size++;
        return true;
    }

    // Returns true if this set contains the specified element
    public boolean contains(String element) {

        int index = hashFunction(element.hashCode());
        Entry current = buckets[index];

        while (current != null) {
            // check if node contains element
            if (current.key.equals(element)) {
                return true;
            }
            // otherwise visit next node in the bucket
            current = current.next;
        }

        // no element found
        return false;
    }

    // Returns the number of elements in this set
    int size() {
        return size;
    }
}

// Main program:

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {

        MyHashSet myHashSet = new MyHashSet(1000);
        Scanner sc = new Scanner(System.in);

        // Step 1: load our txt file of English words.
        try {
            BufferedReader rd = new BufferedReader(new FileReader("words.txt"));
            String currentLine = null;
            while ((currentLine = rd.readLine()) != null) {
            myHashSet.add(currentLine);
            }
        } catch (IOException e) {
            System.out.println("Exception loading words.txt. " + e);
        }

        // Step 2: read the sentence given into an array of strings
        String[] sentenceWords;
        String input = sc.nextLine();
        if (input.equals("")) {
            sentenceWords = new String[0];
        } else {
            sentenceWords = input.split(" ");
        }

        // Step 3: print all misspelled words
        for (String word : sentenceWords) {
            if (!myHashSet.contains(word)) {
                System.out.println(word);
            }
        }
    }
}