Using Binary Trees to find Anagrams

Question

I am currently trying to create a method that uses a binary tree that finds anagrams of a word inputted by the user.

If the tree does not contain any other anagram for the word (i.e., if the key was not in the tree or the only element in the associated linked list was the word provided by the user), the message "no anagram found " gets printed For example, if key "opst" appears in the tree with an associated linked list containing the words "spot", "pots", and "tops", and the user gave the word "spot", the program should print "pots" and "tops" (but not spot).

public boolean find(K thisKey, T thisElement){
    return find(root, thisKey, thisElement);
}

public boolean find(Node current, K thisKey, T thisElement){
    if (current == null)
        return false;
    else{
        int comp = current.key.compareTo(thisKey);
        if (comp>0)
            return find(current.left, thisKey, thisElement);
        else if(comp<0)
            return find(current.right, thisKey, thisElement);
        else{
            return current.item.find(thisElement);
        }
    }
}

While I created this method to find if the element provided is in the tree (and the associated key), I was told not to reuse this code for finding anagrams.

K is a generic type that extends Comparable and represents the Key, T is a generic type that represents an item in the list.

If extra methods I've done are required, I can edit this post, but I am absolutely lost. (Just need a pointer in the right direction)

Answer 1

It's a little unclear what exactly is tripping you up (beyond "I've written a nice find method but am not allowed to use it."), so I think the best thing to do is start from the top.

I think you will find that once you get your data structured in just the right way, the actual algorithms will follow relatively easily (many computer science problems share this feature.)

You have three things:

1) Many linked lists, each of which contains the set of anagrams of some set of letters. I am assuming you can generate these lists as you need to.

2) A binary tree, that maps Strings (keys) to lists of anagrams generated from those strings. Again, I'm assuming that you are able to perform basic operations on these treed--adding elements, finding elements by key, etc.

3) A user-inputted String.

Insight: The anagrams of a group of letters form an equivalence class. This means that any member of an anagram list can be used as the key associated with the list. Furthermore, it means that you don't need to store in your tree multiple keys that point to the same list (provided that we are a bit clever about structuring our data; see below).

In concrete terms, there is no need to have both "spot" and "opts" as keys in the tree pointing to the same list, because once you can find the list using any anagram of "spot", you get all the anagrams of "spot".

Structuring your data cleverly: Given our insight, assume that our tree contains exactly one key for each unique set of anagrams. So "opts" maps to {"opts", "pots", "spot", etc.}. What happens if our user gives us a String that we're not using as the key for its set of anagrams? How do we figure out that if the user types "spot", we should find the list that is keyed by "opts"?

The answer is to normalize the data stored in our data structures. This is a computer-science-y way of saying that we enforce arbitrary rules about how we store the data. (Normalizing data is a useful technique that appears repeatedly in many different computer science domains.) The first rule is that we only ever have ONE key in our tree that maps to a given linked list. Second, what if we make sure that each key we actually store is predictable--that is we know that we should search for "opts" even if the user types "spot"?

There are many ways to achieve this predictability--one simple one is to make sure that the letters of every key are in alphabetical order. Then, we know that every set of anagrams will be keyed by the (unique!) member of the set that comes first in alphabetical order. Consistently enforcing this rule makes it easy to search the tree--we know that no matter what string the user gives us, the key we want is the string formed from alphabetizing the user's input.

Putting it together: I'll provide the high-level algorithm here to make this a little more concrete.

1) Get a String from the user (hold on to this String, we'll need it later)

2) Turn this string into a search key that follows our normalization scheme (You can do this in the constructor of your "K" class, which ensures that you will never have a non-normalized key anywhere in your program.)

3) Search the tree for that key, and get the linked list associated with it. This list contains every anagram of the user's input String.

4) Print every item in the list that isn't the user's original string (see why we kept the string handy?)

---

Takeaways:

Frequently, your data will have some special features that allow you to be clever. In this case it is the fact that any member of an anagram list can be the sole key we store for that list.

Normalizing your data give you predictability and allows you to reason about it effectively. How much more difficult would the "find" algorithm be if each key could be an arbitrary member of its anagram list?

Corollary: Getting your data structures exactly right (What am I storing? How are the pieces connected? How is it represented?) will make it much easier to write your algorithms.

Answer 2

What about sorting the characters in the words, and then compare that.