Given a list L of words, one can define an undirected graph, called a WordGraph on the set of words as follows. We have one vertex for each word, and an edge between two words word1 and word2 if one can transform one of the words to the other via a character insertion or a character substitution.

For example, suppose L = [pain, gain, pan, span, gait, wait]. In the corresponding WordGraph, (pain, gain) is an edge because we can substitute the character `p' in `pain' with a `g' to obtain `gain'. The pair (pain, pan) is an edge because we can insert `i' in `pan' to obtain `pain'.

In the example, the edge set is {(pain, gain), (pain, pan), (gain, gait), (pan, span), (gait, wait)}.

Write a WordGraph class (in either Java or Python) with the following functionality:

• A constructor that takes as input a list of words, and builds the corresponding WordGraph. The type of the input list of words is a List of String.
• A function/method numberOfComponents() that returns the number of connected components in the WordGraph. Thus, if w is a WordGraph object, then w.numberOfComponents() should return the number of connected components of w.
• A function shortestPath(word1, word2) that takes as input two words word1 and word2 (whose type is String) and returns the list of words in a shortest path between word1 and word2 in the WordGraph. If w is a WordGraph object for our example, then w.shortestPath("pain", "span") should return the list [pain, pan, span].

You may assume that words only have characters from the English alphabet, and we don't distinguish upper and lower case letters. For testing, we plan to use subsets from the Stanford GraphBase's list of five-letter words. Please test your program on this list to check if the functions complete in a reasonable amount of time. We will also test on other hand-crafted lists.

I will post submission instructions a bit later here, and any additional clarifications as needed. The homework is due on Tuesday, October 3.

Update: Please upload the source files for your assignment to the Homework3 folder in ICON.