Algorithms and Data Structures

In many situations, we may need to find a word based on one or more letters in it. For example, when making or completing a crossword you may want to find a word that has 4 letters, starts with J and ends with A. In this assignment, the program you will write will create a lexicon of words from various sources (that is, from various text files) and will allow the user to search for words that fit particular patterns. The operational definition of what is taken to be a word will be given later in this handout. For each word, we also keep the following information: • The frequency: How many times the word appears in the input files • The list of neighbors: A neighbor of a word w is a word that is of the same length and differs from w by only one letter Note: The motivation for this requirement is to make the lexicon capable of supporting the following game. Two words are given – let us called them “start word” and “end word”. The aim is to transform the start word into the end word by changing one letter at a time, subject to the condition that all the intermediate “words” are valid words. Obviously, this game is equivalent to finding a path from the start word to the end word along the edges connecting two neighbors.