Jumble

The class Jumble implements the first algorithm discussed here. The program begins by building a static Map of dictionary entries. The key for each entry is a sorted string of the characters comprising the word. The value is a Set of words that include only those letters. Once the dictionary is built, checking a word proceeds very quickly: The word's characters are sorted, O(n log n), and the sorted string is used to look up the corresponding Set of words in the Map. The lookup itself offers O(1) performance.

Ada implementations of both algorithms may be found here.


package org.gcs.jumble;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Set;
import java.util.TreeSet;

/**
 * Jumble.
 * @see <a href="http://en.wikipedia.org/wiki/Jumble">Jumble</a>
 * @author John B. Matthews
 */
 
public class Jumble {

    private static final int MAX = 250000;
    private static final String NAME = "/usr/share/dict/words";
    private static final Map<String, Set<String>> map =
        new HashMap<String, Set<String>>(MAX);
    static {
        try {
            File file = new File(NAME);
            BufferedReader in = new BufferedReader(
                new InputStreamReader(new FileInputStream(file)));
            String s;
            while ((s = in.readLine()) != null) {
                String sorted = sort(s);
                Set<String> words = map.get(sorted);
                if (words == null) {
                    words = new TreeSet<String>();
                    words.add(s);
                    map.put(sorted, words);
                } else {
                    words.add(s);
                }
            }
        } catch (IOException ex) {
            System.err.println(ex.getMessage());
        }
    }
    
    // Sort the letters of a word
    private static String sort(String s) {
        byte[] ba = s.toLowerCase().getBytes();
        Arrays.sort(ba);
        return new String(ba);
    }

    public static void main(String... args) {
        if (args.length < 1) {
            showHelp();
            print();
        } else {
            for (String word : args) {
                System.out.print(word + ": ");
                Set<String> words = map.get(sort(word));
                if (words != null) {
                    for (String s : words) {
                        System.out.print(s + " ");
                    }
                    System.out.println();
                } else {
                    System.out.println("no match.");
                }
            }
        }
    }

    private static void showHelp() {
        System.out.println(
            "Usage: java -jar Jumble.jar <word> [<word>]");
    }

    // Print all entries with more than one permutation
    private static void print() {
        for (Map.Entry<String, Set<String>> entry : map.entrySet()) {
            Set<String> words = entry.getValue();
            if (words.size() > 1) {
                System.out.print(words.size() + " ");
                for (String s : words) {
                    System.out.print(s + " ");
                }
                System.out.println();
            }
        }
    }
}



Copyright © 2008 John B. Matthews. Distributed under the terms of the GPL
Č
ċ
ď
jumble.jar
(42k)
John Matthews,
Sep 4, 2013, 8:51 AM
Comments