Results 1 to 3 of 3
  1. #1
    Schooling is offline Member
    Join Date
    May 2012
    Posts
    14
    Rep Power
    0

    Default Anagram solver help using recursive backtracking

    Okay so I have to write a class that takes a string passed in and solves all of the anagrams for that phrase(I just have to write the class that handles the main, as the instructor already wrote the main method in a class for us. I am a little lost on where to go after getting past the constructor. We have to write the following methods:

    public Anagrams(Set<String> dictionary)
    In this constructor you should initialize a new anagram solver over the given dictionary of words. You may assume that
    the words in the set are in alphabetical order. Do not modify the set passed to your constructor.
    You should throw an IllegalArgumentException if the set passed is null.


    public Set<String> getWords(String phrase)
    In this method you should return a set containing all words from the dictionary that can be made using some or all of the
    letters in the given phrase, in alphabetical order. For example, if your anagram solver is using the dictionary
    corresponding to dict1.txt and you are passed the phrase "Barbara Bush", you should return a set containing the
    elements [abash, aura, bar, barb, brush, bus, hub, rub, shrub, sub].
    You should throw an IllegalArgumentException if the string is null.


    public void print(String phrase)
    In this method you should use recursive backtracking to find and print all anagrams that can be formed using all of the
    letters of the given phrase, in the same order and format as in the example log on the previous page. For example, if your
    anagram solver is using the dictionary corresponding to dict1.txt and you are passed the phrase "hairbrush", your
    method should produce the following output:
    [bar, huh, sir]
    [bar, sir, huh]
    [briar, hush]
    [huh, bar, sir]
    [huh, sir, bar]
    [hush, briar]
    [sir, bar, huh]
    [sir, huh, bar]
    You should throw an IllegalArgumentException if the string is null. An empty string generates no output.


    public void print(String phrase, int max)
    In this method you should use recursive backtracking to find and print all anagrams that can be formed using all of the
    letters of the given phrase and that include at most max words total, in the same order and format as in the example log on
    the previous page. For example, if your anagram solver is using the dictionary corresponding to dict1.txt and this
    method is passed a phrase of "hairbrush" and a max of 2, your method should produce the following output:
    [briar, hush]
    [hush, briar]
    If max is 0, print all anagrams regardless of how many words they contain. For example, if using the same dictionary and
    passed a phrase of "hairbrush" and a max of 0, the output is the same as that shown earlier on this page with no max.
    You should throw an IllegalArgumentException if the string is null or if the max is less than 0. An empty string
    generates no output.
    The provided AnagramMain program calls your methods in a 1-to-1 relationship, calling getWords every time before
    calling print. But you should not assume any particular order of calls by the client. Your code should still work if the
    methods are called in any order, any number of times.
    Java Code:
    We also have a helper class to use to help us accomplish this. It contains the following methods:
    
    public LetterInventory(String s) --- constructs a letter inventory for the given string
    
    public void add(LetterInventory li)
    public void add(String s)    ---  adds the letters of the given string/inventory to this one
    
    public boolean contains(LetterInventory li)
    public boolean contains(String s)    --- returns true if this inventory contains all letters at least as
    many times as they appear in the given string/inventory
    
    public boolean isEmpty()   --- returns true if the inventory contains no letters
    
    public int size()   --- returns the total number of letters in the inventory
    
    public void subtract(LetterInventory li)
    public void subtract(String s)   ---  removes letters of the given string/inventory from this one;
    throws IllegalArgumentException if not contained
    
    public String toString()   --- string version of inventory, such as "[eehhllort]"
    I am just having trouble getting started with the getWords method and on so any pointing in the right direction is greatly appreciated. Thanks, and here is my extremely empty code atm:

    Java Code:
    import java.util.Set;
    import java.util.TreeSet;
    
    
    public class Anagrams {
    	private Set<String> anagramDict;
    	public Anagrams(Set<String> dictionary){
    		if (dictionary == null){
    			throw new IllegalArgumentException();
    		}
    		anagramDict = new TreeSet<String>(dictionary);
    	}
    	
    	public Set<String> getWords(String phrase){
    		if (phrase == null){
    			throw new IllegalArgumentException();
    		}
    		
    	return null;	
    	}
    	
    	public void print(String phrase){
    		
    	}
    	
    	public void print(String phrase, int max){
    		
    	}
    }

  2. #2
    quad64bit's Avatar
    quad64bit is offline Moderator
    Join Date
    Jul 2009
    Location
    VA
    Posts
    1,323
    Rep Power
    7

    Default Re: Anagram solver help using recursive backtracking

    So, your getWords() method takes a string, and returns a set of strings. Why might one convert a string into a set of strings and how might one go about it? If you were doing it on paper, how would you do it?

  3. #3
    Schooling is offline Member
    Join Date
    May 2012
    Posts
    14
    Rep Power
    0

    Default Re: Anagram solver help using recursive backtracking

    Quote Originally Posted by quad64bit View Post
    So, your getWords() method takes a string, and returns a set of strings. Why might one convert a string into a set of strings and how might one go about it? If you were doing it on paper, how would you do it?
    Well I am not sure but I don't think I need to do that. I think I just have to compare String phrase with the "dictionary" file that the main handles to produce the options of anagrams. I think I would have to instanciate a Set and convert the original set that the constructor is passed to strings to compare to String phrase and then put the strings into the Set I instanciated inside the getWords method and return it. I just don't know how I will compare them to see if it's an anagram. Is it as simple as using the String .contains method?

Similar Threads

  1. Recursion Backtracking
    By 6thDAY in forum Advanced Java
    Replies: 1
    Last Post: 03-28-2011, 05:06 PM
  2. Backtracking
    By pali185 in forum New To Java
    Replies: 2
    Last Post: 12-17-2010, 02:08 PM
  3. need help with backtracking
    By Dumisan in forum Advanced Java
    Replies: 9
    Last Post: 02-17-2010, 02:02 PM
  4. Recursive Anagram
    By zoe in forum Advanced Java
    Replies: 1
    Last Post: 08-07-2007, 07:15 AM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •