This assignment will give you practice with recursive backtracking. You are to c
ID: 3551308 • Letter: T
Question
This assignment will give you practice with recursive backtracking. You are to create a class called AnagramSolver that uses a dictionary to find all combinations of words that have the same letters as a given phrase (see the sample log for examples). Your class must include the following public methods. Your print method must produce the anagrams in the same format as in the sample log. The easiest way to do this is to build up your answer in a List or Stack or Queue. Then you can simply "println the structure and it will have the appropriate format. You are required to solve this problem by using recursive backtracking. In particular, you are to write a recursive method that builds up an answer one word at a time. On each recursive call, you are to search the dictionary from beginning to end and to explore each word that is a match for the current set of letters. The possible solutions are to be explored in dictionary order. For example, in deciding what word might come first, you are to examine the words in the same order in which they appear in the dictionary. The solution to the 8 queens problem provides a good example to follow for your own code. The primary difference in the recursion is that in 8 queens, we stopped as soon as we found an answer, whereas in the anagrams program you are to produce all answers. An important aspect of the 8 queens solution was the separation of the recursive code (Queens .java) from the code that managed low-level details of the problem (Board.java). You are required to follow a similar strategy here. The low-level details for the anagram problem involve keeping track of various letters and figuring out when one group of letters can be formed from another group of letters. It turns out that the Letter Inventory' class that we wrote for assignment 1 provides us with the low-level support we need (review handout #3 to remind yourself of the available methods). For any given word or phrase, what matters to us is how many of each letter there are. Recall that this is exactly what theExplanation / Answer
// Programming Assignment #1
// LetterInventory.java
// In this programming assignment you will practice using arrays and classes.
public class LetterInventory {
private int total;
private int[] count;
// Constructs an inventory (a count) of the alphabetic letters in the given string
public LetterInventory(String data) {
total = 0;
count = new int[26];
for (int i = 0; i < data.length(); i++) {
char ch = Character.toLowerCase(data.charAt(i));
if (ch >= 'a' && ch <= 'z') {
total++;
count[ch - 'a']++;
}
}
}
// Returns a count of how many of this letter are in the inventory.
public int get(char letter) {
char ch = Character.toLowerCase(letter);
if (!(ch >= 'a' && ch <= 'z'))
throw new IllegalArgumentException("Invalid letter");
return count[ch - 'a'];
}
// Sets the count for the given letter to the given value.
public void set(char letter, int value) {
char ch = Character.toLowerCase(letter);
if (!(ch >= 'a' && ch <= 'z'))
throw new IllegalArgumentException("Invalid letter");
if (value < 0)
throw new IllegalArgumentException("Invalid value");
total -= count[ch - 'a'];
count[ch - 'a'] = value;
total += value;
}
// Return the sum
public int size() {
return total;
}
// Returns true if this inventory is empty
public boolean isEmpty() {
return total == 0;
}
// Returns a String representation of the inventory
public String toString() {
String result = "[";
for (int i = 0; i < count.length; i++) {
for (int c = 0; c < count[i]; c++) {
result = result + (char)('a' + i);
}
}
result = result + "]";
return result;
}
// Constructs and returns a new LetterInventory object after add the argument
public LetterInventory add(LetterInventory other) {
LetterInventory result = new LetterInventory("");
result.total = total + other.total;
for (int i = 0; i < 26; i++)
result.count[i] = count[i] + other.count[i];
return result;
}
// Constructs and returns a new LetterInventory object after subtract the argument
public LetterInventory subtract(LetterInventory other) {
LetterInventory result = new LetterInventory("");
result.total = total - other.total;
boolean valid = true;
for (int i = 0; i < 26 && valid; i++) {
result.count[i] = count[i] - other.count[i];
if (result.count[i] < 0)
valid = false;
}
if (!valid)
result = null;
return result;
}
// check whether contains the argument
public boolean contains(LetterInventory other) {
for (int i = 0; i < count.length; i++)
if (count[i] < other.count[i])
return false;
return true;
}
}