Member Avatar for coroll

Hi,

I want to find all the words(scabble words) that can be made out of given set of letters.
ex: abnana

results: a aa ab an baa ban banana na nab

How could i achieve this? Do i need a binary tree?
Plz some one help me...

  • 5 Contributors
  • 15 Replies
  • 2K Views
  • 5 Years Discussion Span
  • Latest Post Latest Post by JamesCherrill

Dani AI

Generated

You do not need permutations or a binary tree here. Treat the rack as a multiset of letters and check each dictionary word against it. was on the right track with frequencies, but you must compare required counts for every letter, not just presence. ’s sorted-key index is great for exact anagrams; for the general Scrabble rack problem, a simple count-array check is both clearer and faster.

Here is a minimal Java approach that handles repeated letters correctly and short-circuits early. Complexity is O(26) per word after counting, so it scales to large dictionaries.

// Build letter counts for the rack once
static int[] countLetters(String s) {
    int[] c = new int[26];
    for (int i = 0; i < s.length(); i++) {
        char ch = Character.toLowerCase(s.charAt(i));
        if (ch >= 'a' && ch <= 'z') c[ch - 'a']++;
    }
    return c;
}

// Return true if 'word' can be formed from the rack letters (with multiplicity)
static boolean canMake(String word, int[] rack) {
    int[] need = new int[26];
    for (int i = 0; i < word.length(); i++) {
        char ch = Character.toLowerCase(word.charAt(i));
        if (ch < 'a' || ch > 'z') continue;
        int idx = ch - 'a';
        need[idx]++;
        if (need[idx] > rack[idx]) return false; // fail fast
    }
    return true;
}

// Example usage:
// int[] rack = countLetters("abnana");
// for (String w : dictionary) if (w.length() <= 6 && canMake(w, rack)) results.add(w);

Notes:

  • This fixes ’s concern: a word like zoo will be rejected because it needs two o’s; ban will pass, banana will pass only if the rack has enough a’s and n’s.
  • Filter by length first (w.length() <= rackSize) to skip obvious non-matches.
  • If you later want exact anagrams, pre-index the dictionary by sorted-letter signature as suggested, and compare sorted(word) to sorted(rack) via a two-pointer subsequence test instead of generating permutations.

Recommended Answers

All 15 Replies

Member Avatar for deceptikon

This seems more like a job for a frequency list. You can use a dictionary of characters and counts like so:

for each word in the dictionary
    build a frequency list of each character initialized to 0

    for each character in the letter collection
        if the character exists in the frequency list
            increment the count for that character

    if all counts in the frequency list are greater than 0
        mark the word as a match
Member Avatar for deceptikon

I think the question is actually "how do I generate permutations?"

"nab" isn't a permutation of "abnana". Permutations can get you closer to a complete solution, but that's not all there is to it.

Member Avatar for coroll

Im a student so Im not expert in java.But not even too much low.
I dont understand the frequency list.
If u could please explain the psuedo code a bit?

Member Avatar for deceptikon

I dont understand the frequency list.

http://en.wikipedia.org/wiki/Letter_frequencies.

If u could please explain the psuedo code a bit?

You're basically just matching at least one of every letter in a given word using the available tiles that the player currently has. All of the words that meet this requirement are words that the player can make with his or her tiles.

Member Avatar for JamesCherrill

Probably the easiest way is to put all the words in a TreeMap (for fast searching) then check every permutation of every subset of your letters to see if it's in the TreeSet. However that will generate a lot of searches if you have a lot of letters, which may or may not make it too slow.

You can speed up the search, at the cost of more work at startup time, by building a TreeMap. For each word sort its letters into order and use that as the key; the word (or words)corresponding to that form the value. Now you just need to test each subsets of your letters once - keep them sorted and see if the subset is a valid key. There's no need to test all the permutations.

Decepticon's solution may be faster or easier than either of these, but I'm ashamed to admit that I don't understand it.

Member Avatar for deceptikon

Decepticon's solution may be faster or easier than either of these, but I'm ashamed to admit that I don't understand it.

Here's a quickie example to show what I mean. Please excuse the crappy Java, I'm terribly rusty:

import java.util.*;

class Foo {
    public static void main(String args[])
    {
        String[] dictionary = {
            "za",  "zoo", "a",      "aa", "ab",  "an", 
            "baa", "ban", "banana", "na", "nab", "test"
        };
        String word = "abnana";

        for (int i = 0; i < dictionary.length; i++) {
            TreeMap<Character, Integer> freq = new TreeMap<Character, Integer>();

            for (int j = 0; j < dictionary[i].length(); j++)
                freq.put(dictionary[i].charAt(j), 0);

            for (int j = 0; j < word.length(); j++) {
                if (freq.containsKey(word.charAt(j)))
                    freq.put(word.charAt(j), freq.get(word.charAt(j)) + 1);
            }

            boolean match = true;

            for (int count : freq.values()) {
                if (count <= 0) {
                    match = false;
                    break;
                }
            }

            if (match)
                System.out.println("'" + dictionary[i] + "' was found");
        }
    }
}
Member Avatar for JamesCherrill

OK, thank you. That seems functionally equivalent to creating a key that contains the letters in the word but sorted - ie its a way of identifying words that is independent of the order in which its letters appear. (Correct me if I'm wrong, please.)

Member Avatar for deceptikon

ie its a way of identifying words that is independent of the order in which its letters appear.

Yes, pretty much.

Member Avatar for gusano79

"nab" isn't a permutation of "abnana". Permutations can get you closer to a complete solution, but that's not all there is to it.

True, you'd also need to look at subsets of the original set of letters.

For completeness, you'd also want to consider a nonempty game board, which would involve finding words with specific letters in fixed positions.

Edited by gusano79 because: flow
Member Avatar for coroll

Here's a quickie example to show what I mean. Please excuse the crappy Java, I'm terribly rusty:

Thank you very much.
I get it now and you just saved me :-)

Member Avatar for Todor

Hello, i tried implementing your solution . I am doing similar project like the author posted, but the thing with your code is it doesn't count for repeated letters, so word ban, will give banana from dictionary, which is not valid. Does anyone know how to sort this problem out.
Thanks for your response in advance.

Member Avatar for JamesCherrill

After that discussion I implemented a general version that works correctly. It takes each word in the dictionary and sorts its letters into ascending order then adds that to a Map (sorted letters as key, list of matching original words as value).
To make searching faster I actually created an array of maps, one for each word length, but that's maybe over-thinking it.

Edited by JamesCherrill
Member Avatar for Todor

Thats pretty cool idea, thanks :)

Member Avatar for JamesCherrill

Yes.
I was amazed by the performance. Loading the map with over a quarter of a million words from an official scrabble list takes under a second. Searching for anagrams goes as fast as you can type (which you would expect with a tree map), but searching the original strings for words with some specified letters in particular places is also seemingly instant. I didn't implement searching for anagrams with specified letters in specific places, but that woud be very easy and also instant.

Edited by JamesCherrill
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.