CODEWITHSUNDEEP
javastringrecursionarraylistanagram
andrewktmeikle
andrewktmeikle

Reputation: 487

Strings & possible anagrams of those strings

I'm doing a wee project (in Java) while uni is out just to test myself and I've hit a stumbling block.

I'm trying to write a program that will read in from a text version of dictionary, store it in a ds (data structure), then ask the user for a random string (preferably a nonsense string, but only letters and -'s, no numbers or other punctuation - I'm not interested in anything else), find out all the anagrams of the inputted string, compare it to the dictionary ds and return a list of all the possible anagrams that are in the dictionary.

Okay, for step 1 and 2 (reading from the dictionary), when I'm reading everything in I stored it in a Map, where the keys are the letter of the alphabet and the values are ArrayLists storing all the words beginning with that letter.

I'm stuck at finding all the anagrams, I figured how to calculate the number of possible permutations recursively (proudly) and I'm not sure how to go about actually doing the rearranging.

Is it better to break it up into char and play with it that way, or split it up and keep it as string elements? I've seen sample code online in different sites but I don't want to see code, I would to know the kind of approach/ideas behind developing the solution for this as I'm kinda stuck how to even begin :(

I mean, I think I know how I'm going to go about the comparison to the dictionary ds once I've generated all permutations.

Any advice would be helpful, but not code if that'd be alright, just ideas.

P.S. If you're wanting to see my code so far (for whatever reason), I'll post what I've got.

Upvotes: 0

Views: 3097

Answers (3)

if_zero_equals_one
if_zero_equals_one

Reputation: 1774

public String str = "overflow";
public ArrayList<String> possibilities = new ArrayList<String>();
public void main(String[] args)
{
    permu(new boolean[str.length()],"");
}
public void permu(boolean[] used, String cur)
{
    if (cur.length()==str.length())
    {
        possibilities.add(cur);
        return;
    }
    for (int a = 0; a < str.length(); a++)
    {
        if (!used[a])
        {
            used[a]=true;
            cur+=str.charAt(a);
            permu(used,cur);
            used[a] = false;
            cur = cur.substring(0,cur.length()-1);
        }
    }
}

Simple with a really horrible run-time but it will get the job done.

EDIT : The more advanced version of this is something called a Dictionary Trie. Basically it's a Tree in which each node has 26 nodes one for each letter in the alphabet. And each node also has a boolean telling whether or not it is the end of a word. With this you can easily insert words into the dictionary and easily check if you are even on a correct path for creating a word.

I will paste the code if you would like

Upvotes: 4

aioobe
aioobe

Reputation: 420921

Computing the permutations really seem like a bad idea in this case. The word "overflow" for instance has 40320 permutations.

A better way to find out if one word is a permutation of another is to count how many times each letter occur (it will be a 26-tuple) and compare these tuples against each other.

Upvotes: 3

Jay
Jay

Reputation: 27464

It might be helpful if you gave an example to clarify the problem. As I understand it, you are saying that if the user typed in, say, "islent", the program would reply with "listen", "silent", and "enlist".

I think the easiest solution would be to take each word in your dictionary and store it with both the word as entered, and with the word with the letters re-arranged into alphabetical order. Let's call this the "canonical value". Index on the canonical value. Then convert the input into the canonical value, and do a straight search for matches.

To pursue the above example, when we build the dictinoary and saw the word "listen", we would translate this to "eilnst" and store "eilnst -> listen". We'd also store "eilnst -> silent" and "eilnst -> enlist". Then we get the input string, convert this to "eilnst", do a search and immediately find the three hits.

Upvotes: 2

Related Questions