The AnagramSolver class is responsible for recursively trying permutations of a

Question

The AnagramSolver class is responsible for recursively trying permutations of a word and checking to see if it's in a Dictionary. It should take a Dictionary object in the constructor. It will use this list when attempting to solve an anagram. Your AnagramSolver class will have a solve method that accepts a String and returns the solved String (or null if there is no solution). You may find it useful to use a helper method to make your recursive solution. In your recursive solution, you must use the Dictionary's contains method to see if a generated string is a word or not.

When the solve method is called, you should use recursion to find a solution to the anagram. To do this, you will need to reorder the characters given to you into every possible combination and try each of them. You only need to return the first solution to the anagram (if there are multiple solutions possible

I need some help with creating the method for this program, the way I'm trying doesn't seem to be working. If anyone could show me a different way to do this it would be great.

Explanation / Answer

I don't know what programming language you're using, so I'll write the answer in pseudocode:

// Tests whether there is a word consisting of startchars plus some permutation of charsToPermute
// For instance if startchars is "be" and charsToPermute is "sra" and "bears" is in the dictionary,
// then solvableStartingWith will return "bears"
// If there is no such word then return null

define solvableStartingWith(startchars, charsToPermute):
    // base case in the recursion
    if charsToPermute == ""
        if dictionary.contains(startchars) return startchars, else return null

    // Recursion:
    // For each character in charsToPermute
    // see if there's a word in the dictionary that starts with
    // the given startChars plus that character
    // For instance if startchars is "be" and charsToPermute is "sra"
    // check if the dictionary has a word starting with "bes" and ending with some permutation of "ra"
    // check if the dictionary has a word starting with "ber" and ending with some permutation of "sa"
    // and check if the dictionary has a word starting with "bea" and ending with some permutation of "sr"

    for (char in charsToPermute):
         remainingCharsToPermute = charsToPermute with char removed
         wordFound = solvableStartingWith(startchars+char, remainingCharsToPermute)
         if wordFound != null
             return wordFound

    // If our search hasn't returned a word, then return null
    return null

define solve(word):
    return solvableStartingWith("",word)

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.