In this assignment, you’ll create an Anagram Finder. Two phrases are anagrams of one another if they contain exactly the same letters. For example, “Vile” and “Evil” are a simple anagram. Other examples are “Bad Credit” and “Debit Card,” as well as “Dormitory” and “Dirty room.”
This program accepts a word or phrase from the user and a maximum number of words for the anagram. It then lists all the anagrams that can be created from that phrase within the limited number of words. The main method is written for you, as are some helper methods in the Utils class. There are three dictionaries provided, 1 is the simplest/shortest (57 words), to be used mostly for debugging, while 2 is larger (nearly 4000 words) for testing the program with larger word sets, and 3 has the most (almost 20,000 words) for getting a more complete list of anagrams.
The phrase that the user enters has been stripped of spaces and punctuation, and converted to lower case so that you can more easily use your dictionary (which is also only in lower-case).
Your task is to write the findAlgorithms method. This method takes three parameters, a string with the phrase to search for algorithms in, a number with the largest number of words to use in a solution, and a list of strings (the words in the dictionary to search). The method returns a list of strings, the anagrams that the method found.
This method should be written recursively. Start by thinking about how to search for anagrams that are one word (which does not need to be recursive) and then use recursion to expand that to multiple words. To avoid the search taking too long, this method should limit its depth—if the user enters 3, for example, it shouldn’t search for anagrams longer than three words. This will impact your recursive step and your base case—if the user enters a depth of 1, your method should know not to do recursion. For larger depths, your method will use recursion, but the depth of each call will be 1 smaller.
There are two methods in the Utils class that are particularly helpful for you: contains and removeCharacters. contains will tell you if the first string’s letters can be found in the second string. For example, contains(“dirty”, “dormitory”) would return true. removeCharacters will return the second String without the characters from the first String—for example, removeCharacters(“dirty”, “dormitory”) would return “omor”.
For testing your program, remember that your input phrase does not need to be valid English. You can type in any combination of letters to make sure you test the anagram you’re looking to find.