Write a complete Java program that computes the edit distance between two words. Edit distances are useful in applications that need to determine how similar two strings are, such as spelling checkers. The edit distance between two strings is the minimum number of operations that are needed to transform one string into the other. For this program, an operation is a substitution of a single character, such as from brisk to brick. For example, the edit distance between the words dog and cat is 3, following the chain of cog, cot, and cat to transform dog into cat. When you compute the edit distance between two words, each immediate word must be an actual valid word (i.e., use dict.txt to get a list of valid words). Read your input from a dictionary text file (dict.txt). From this file, compute a map from every word to its immediate neighbors, that is, the words that have an edit distance of 1 from it. Once this map is built, you can walk it to find paths from one word to another. A good way to process paths to walk the neighbor map is to use a list of words to visit (i.e., a queue), starting with the beginning of word, such as dog. Your algorithm should repeatedly remove the front word of the queue and add all of its neighbors to the end of the queue, until the ending word (e.g., cat) is found or until the queue becomes empty, which indicates that no path exists between the two words.
Examples (the underlined text indicates user input):
Welcome to the edit distance calculator
Initializing dictionary...
Please enter two words (or 0 to quit): dog cat
Edit distance: 3
Please enter two words (or 0 to quit): house glass
Edit distance: 12
Please enter two words (or 0 to quit): course across
Edit distance: no path exists
Please enter two words (or 0 to quit): gone wild
Edit distance: 5
Please enter two words (or 0 to quit): house goose
Edit distance: 3
Please enter two words (or 0 to quit): edit gone
Edit distance: no path exists
Please enter two words (or 0 to quit): dkjfk jkdjfkdj
Input word(s) not found in the dictionary
Please enter two words (or 0 to quit): 0