Two distinct words can be joined if one, two or three of the letters at the end of the first word are the same as the letters at the beginning of the second word, and only if the letter/letters are in the same order.

FOR EXAMPLE:

Appleand pleasantcan be joined to form appleasant.
Grilland lammacan be joined to form grillama.
Predicamentand tensioncan be joined to form predicamentatension.

A word-snake of lengthn is a sequence of n words that can be joined each to the next to form one long string. Write a Java program that prompts the user to enter the name of the data file whose first record is a positive integer n(n<30)followed by n lines each containing a single word. The words consist only of lower-case letters, and are at least 4 letters longand are in alphabetical order.

Treat the problem as a directed graph with n nodes, where nodes representwords, and an edge from node i to node jmeans that word i and word j can be joined. A word cannot be adjacent to itself, even a word like outshout. Your program should prompt the user to enter two words (in lower case) at the keyboard and then write to the screen a single line of output something like one of the following:

You entered a word that is not in the list.
(Stop the program if this happens.)

The words "apple" and "telephone" are not connected.
(Print this if there is no word-snake beginning with "apple" and ending with "telephone".)

The shortest snake that begins with "apple" and ends with "telephone" has length 52.
(Print this if "apple" is connected to "telephone", and the shortest path connecting them is of length 51. You do not have to give the words that make up the word-snake.)

You will need a method that determines whether two words can be joined or not. This is a directed graph, so word i may be adjacent to word j without word j being adjacent to word i. There are pairs of words (like chairand ironic) where each is adjacent to the other, but this rarely happens.

Sometimes words can be joined in more than 1 way, like "phenomenon" and "nonsense". These two words can be joined by the single letter ‘n' or by the substring"‘non". In such cases the only thing that matters is that they can be joined. As stated above, in this problem we do not allow a word to be joined to itself even if it begins and ends with the same letter(s), such as "chronic" or "sturdiest". However, we do allow a word to be connected to itself, i.e. a word-snake of length 3 or more may begin and end with the same word, as seen by the following word-snake of length 5.

Attachment:- Program-3-Original2.docx