Write a recursive method named squishWord that uses backtracking to try to find a way to "squish" a word down to an empty string, one letter at a time.
Your method accepts two parameters: a string representing the word to try to "squish", and a Set of strings representing the English dictionary.
"Squishing" a word is defined as finding a way to repeatedly remove a single letter from the word, forming another string that is a valid English word at each step, until the string is empty.
If your method is able to find a valid "squish" sequence, your method should print it in the format shown below: each word in the sequence is shown in order, starting with the original word passed in, with a space between words.
For example, here is a sequence of removals that can squish the word "startling":
startling starting staring string sting sing sin in i
Note that you cannot just remove any letter; if you removed the "a" in the first step, you'd get "strtling", which is not a valid English word.
Each word along the way must be an English word from the dictionary for the sequence to be valid.
If there are multiple ways to "squish" the word, you should find and print only one of them.
After printing one path, your code should stop without printing any other potential paths.
If the string passed to your method is not a single valid English word, or if it is not possible to produce to "squish" the given string, your method should print:
No sequence found.
Assume that the dictionary has already been read from a file and contains all legal English words.
You do not need to worry about any case sensitivity issues for this problem; all words will be in lowercase.
Constraints:
Do not declare any global variables.
You can use any data structures you like, and your code can contain loops, but the overall algorithm must be recursive and must use backtracking.
You are allowed to define other "helper" methods if you like; they are subject to these same constraints.
Do not modify the state of the set passed in.
