Can you help me with this in Java, Please? Thank You so much. This problem is related to recursion. The instruction is all in the pictures below and I will copy and paste all of the starter code for you below. Basically, all you have to do is to add code into these files: LongestFinder.java , WordSplitPrinter.java , WordSpiltChecker.java in order to create the given output. There are too many words inside of the words.txt files, I can't upload here. You can ignore the words.txt part and just add code into the given files above. Thank You so much.

LongestFinder.java

package edu.csc220.recursion; import java.util.ArrayList; public class LongestFinder { /** Returns the longest String in the list words. If there is a tie, any of the Strings can be returned. */ public String findLongest(ArrayList words) { // TODO: Implement this. return ""; } public static void main(String[] args) { LongestFinder longestFinder = new LongestFinder(); ArrayList words = new ArrayList(); words.add("apple"); words.add("banana"); words.add("cat"); words.add("dog"); words.add("elephant"); words.add("fish"); words.add("gin"); // Expected to print out "Longest: elephant". System.out.println("Longest: " + longestFinder.findLongest(words)); } }

WordSplitPrinter.java

package edu.csc220.recursion; import java.io.*; import java.util.*; public class WordSplitPrinter { /** * Finds and prints out every possible way to split the input String into individual, valid English words (including * if input is itself a single valid word). You must call printWordSplit below to actually print out the results. */ public void findWordSplits(String input, TreeSet allWords) { // TODO: Implement this. } /** Prints out a word split, i.e. one particular arrangement of words. This is implemented for you! */ private void printWordSplit(ArrayList words) { if (words.isEmpty()) { System.out.println("(empty word list)"); } else { System.out.print(words.get(0)); for (int i = 1; i  dictionary = readWords(); WordSplitPrinter wordSplitPrinter = new WordSplitPrinter(); // Expected to print out: // i saw a bus // i saw ab us // is aw a bus // is aw ab us wordSplitPrinter.findWordSplits("isawabus", dictionary); } // Reads the "words.txt" file and returns the words in a TreeSet. This is completely implemented for you! private static TreeSet readWords() { TreeSet allWords = new TreeSet(); try { BufferedReader bufferedReader = new BufferedReader(new FileReader("words.txt")); String line; while ((line = bufferedReader.readLine()) != null) { if (line.trim().isEmpty()) { continue; } allWords.add(line.toLowerCase()); } bufferedReader.close(); } catch (IOException exception) { throw new RuntimeException(exception); } return allWords; } }

WordSpiltChecker.java

package edu.csc220.recursion; import java.io.*; import java.util.*; public class WordSplitChecker { /** * Returns true if there is at least one way to split input into a sequence of valid English words (words that * appear in the allWords set), and false otherwise. * * For this assignment, you can define your own private helper method, but you cannot change this method's signature * (i.e. the name, the parameters, or the fact that it returns a boolean). */ public boolean hasWordSplit(String input, TreeSet allWords) { // TODO: Implement this. return false; } public static void main(String[] args) { TreeSet allWords = readWords(); WordSplitChecker wordSplitChecker = new WordSplitChecker(); // All of the following should print out true. System.out.println("goat: " + wordSplitChecker.hasWordSplit("goat", allWords)); System.out.println("car: " + wordSplitChecker.hasWordSplit("goat", allWords)); System.out.println("isawabus: " + wordSplitChecker.hasWordSplit("isawabus", allWords)); // All of the following should print out false. System.out.println("xvix: " + wordSplitChecker.hasWordSplit("xvix", allWords)); System.out.println("m: " + wordSplitChecker.hasWordSplit("m", allWords)); } // Reads the "words.txt" file and returns the words in a TreeSet. This is completely implemented for you! private static TreeSet readWords() { TreeSet allWords = new TreeSet(); try { BufferedReader bufferedReader = new BufferedReader(new FileReader("words.txt")); String line; while ((line = bufferedReader.readLine()) != null) { if (line.trim().isEmpty()) { continue; } allWords.add(line.toLowerCase()); } bufferedReader.close(); } catch (IOException exception) { throw new RuntimeException(exception); } return allWords; } }

words.txt

For this part, You can try using some random English words here

Instruction:

Overview In this assignment, you'll use what you've learned about recursion to solve three problems: 1. A problem which uses "standard" recursion 2. A problem which uses recursion exploration 3. A version of #2 which also uses recursive backtracking If that sounds like a lot, don't worry! Problem 3 will be very closely related to problem 2, and will just require some modifications. Assignment Setup Download the folder named "Recursion Starter Code" from iLearn. It will be downloaded as a .zip file which can be extracted to whatever location you want on your computer. Make sure that the folder structure appears as follows: > Recursion Starter Code-20210222 > java > words.txt The number that appears after "Recursion Starter Code-" is the download date, so it's fine if it's different. If extracting the .zip file directly shows the java folder and words.txt file, then create a "Recursion Starter Code folder and move the "java" folder and "words.txt" into it. Set up an IntelliJ project choosing Recursion Starter Code-20210222 (or similarly named) as the root. For step-by-step instructions on setting up an Intellij project, see the "IntelliJ Setup Guide" handout on iLearn (at the top of the iLearn course page). Once the project is set up, your project navigation panel should look something like this: File Edit View Navigate Code Analyze Refactor Build Run Tools V Recursion Starter Code Project Recursion Starter Code C:\Users\dzhou\Desktop\Recursion Starter Code idea java vedu.csc220.recursion LongestFinder WordSplitChecker WordSplit Printer Recursion Starter Code.iml words.txt > Milli External Libraries PO Scratches and Consoles Make sure that the "words.txt file is included as part of the project. It contains a list of commonly used English words and is used in the word split problems. Please reach out ASAP if you have any problems setting the project up. Detailed Requirements I strongly recommend approaching the three problems in the order described below: first LongestFinder, then WordSplitPrinter, and then finally WordsplitChecker. LongestFinder Material from Lectures 07 and 08 will be helpful here. LongestFinder is a class that defines a method: findLongest. It initially appears as follows: public String findLongest(ArrayList words) { // TODO: Implement this. return""; } You will be replacing the TODO and the placeholder line (return "";) with your own implementation. findLongest should return whichever string in the ArrayList parameter words has the longest length. If there is a tie between words, returning any of them is acceptable. You can assume that words will never be empty. As an example, the main method in the provided starter code runs the following: LongestFinder longestFinder = new LongestFinder(); ArrayList words = new ArrayList(); words.add("apple"); words.add("banana"); words.add("cat"); words.add("dog"); words.add("elephant"); words.add("fish"); words.add("gin"); System.out.println("Longest: " + longestFinder.findLongest(words)); Once you've implemented find Longest correctly, this should print out: Longest: elephant In order to receive credit, you must implement findLongest using recursion. There is, of course, an iterative solution: String longestSoFar = ""; for (String word: words) { if (word.length() > longest SoFar.length()) { longestSoFar = word; } } return longestSoFar; However, as this assignment is a test of your understanding of recursion, you'll need to figure out the recursive solution. For some hints on how to solve the problem, think about how to apply the recursion formula: 1. What are the base cases? o What sort of words list would make it extremely straightforward to figure out the longest string in the list? 2. How can you simplify the problem? Can you call find Longest on a smaller list, for example? 3. How can you relate the solution to the simplified version of the problem to the original o problem? How does calling findLongest on a smaller list help you find the longest string in the entire list? In your solution, you will likely need to know: How to read a string at a specific index in an ArrayList, and how to remove a string from an ArrayList. Review the lecture slides from Lecture 05 to see a summary of the methods you can call on an ArrayList object. How to compare two strings to determine which is longer. You can see an example of the syntax for this above: if (word.length() > longest SoFar.length()) { // In this example, word is longer than longestSoFar. } WordSplit Printer Material from Lecture 09 will be helpful here. In lecture, we talked about how we can use recursion exploration to print out all permutations of a given string. For example, we could use recursion on the input "goat" to print out: tgoa tgao toga goat gota gaot gato gtoa gtao ogat ogta oagt oatg otga otag agot agto aogt aotg atgo atog toag tago taog Most of these aren't actual anagrams, because they're gibberish. We could check which are actual words (like "toga"), but that wouldn't be enough. There are also cases like "atgo" where the full string isn't a word, but we can break it into the separate words "at" and "go". To find all anagrams, then, we need to find the ways we can take one of these permutations and split it into separate English words. That's where your method, findWordsplits, comes in: public void findWordSplits(String input, TreeSet allWords) { // TODO: Implement this. } The method takes two parameters: input and allWords. input will be a string like "atgo" or "goat" that you're trying to split into separate words. You do not need to find permutations of input, since that was part of the demo we did in class. input will be a string whose character ordering is already set. allWords is a set containing the words listed in the "words.txt" file -- nearly 10,000 English words. allWords is already populated for you! You'll need to use it when you're splitting up the input string, since each chunk needs to be an actual word. . Your task is to implement findWordsSplits to find every way you can split input into valid English words, where every character in input is used exactly once. For example, if input is we would expect these two splits to be printed: "goat", go at goat Other arrangements, such as "g oat" or "goat", would not be printed because "g", "goa", and "t" are not considered words. The main method uses "isawabus" as input. Once findWordsSplits is correctly implemented, you should see the following output: i saw a bus i saw ab us is aw a bus is aw ab us If the exact ordering is not the same, that's completely fine. I've provided an already implemented method in the starter code called printWordsplit: public void printWordSplit(ArrayList words) { // Already implemented for you. } You should call printWordSplit to print out a single arrangement. For the "i saw a bus" example above, you would call printWordSplit passing in an ArrayList containing ["i", "saw", "a", "bus" ] to print it out. findWordSplits is a recursion exploration problem, just like our permutations demo in lecture. Think about how to apply the recursion exploration formula: 1. How do you represent a path of options you're exploring? o printWordsplit is a major hint -- if you need an ArrayList to print a word split, that would also be a convenient way to represent a path. 2. At each step, what are your options? o Consider an example like "isawabus". We can actually list out every possible option for the next word: i is isa isaw isawa isawab isawabu isawabus Not all of these are words, so you'll need to check for yourself which ones are valid options using the allWords set. The TreeSet is just a specific type of Set, so you can use any Set methods on it. 3. What do you do when you've finished exploring a path? o Just call printWordsplit! Another hint: in your implementation, you will need to use the String's substring method to split a string into two parts. To get a substring that contains the first i characters, use str.substring(0, i) where str is the name of your String variable. To get the rest of that string (i.e. everything other than the first i characters), use str.substring(i). If you're struggling to translate the above into actual code, I strongly recommend revisiting Lecture 09 and see how we applied the same formula to the permutations problem or the password guessing problem. WordSplitChecker Material from Lecture 10 will be helpful here. If you were able to complete WordSplitPrinter, then congratulations! You've already done most of the hard work for this last step. In WordSplitChecker, you'll find the haswordSplit method: public boolean hasWordSplit(String input, TreeSet allWords) { // TODO: Implement this. return false; } You will be replacing the TODO and the placeholder line (return false;) with your own implementation. hasWordSplit should return true if there is at least one way to split input into valid words (including if the entire string input is a single valid word), and false otherwise. Valid words are those that appear in the allWords set. Notice that the difference between hasWordsplit and findWordsplits is that haswordsplit doesn't need to find every possible way to split input -- it just needs to return true as soon as it finds the first valid split, or false if there are none. Counter-intuitively, hasWordSplit is actually more challenging, for a few reasons: 1. hasWordSplit needs to return a value. That means every recursive call made needs to think about how to use the return value from that call. 2. In order to receive full credit, your implementation of haswordsplit must return a result as soon as it can. hasWordSplit should return true as soon as it finds the first word split, and stop searching for any others, as it is a recursive backtracking problem. 3. In order to receive full credit, your implementation cannot use any instance or global variables. If you need to access some piece of information, it needs to be passed from method to method using parameters and return values. A lot of the recursion exploration logic for hasWordSplit will be the same as what you wrote for findWordsplits. A major difference is that in order to satisfy requirement #2 above, you'll need to add recursive backtracking logic. Think about what it means when you recursively call hasWordSplit when exploring an option, and it returns true. What about when it returns false? Apply the recursive backtracking formula from Lecture 10, and use the demos from Lecture 10 as a reference