Rearranging Letters to Form Word

Question:

Rearranging the letters to form a word is a very funny algorithm problem, and it has several variants. Here we will talk about the problem – the most efficient way to find out whether we can rearrange these letters and form a word, and if yes, return all words that can be constructed.

For input [d, a, e, p, n, p], we can rearrange them into a word "append".

Answers:

We can think about our commonly-used data structure - HashMap, if we can build one HashMap from the dictionary, and then query it using some key, the running time would be O(1). Brilliant!!!

But what would be key and value? 

First the input order doesn't matter, "atc" is same as "tac", or "cta", so we can order the input, "atc", "tac", "cta" would all be sorted as "act".

Also we may construct several words from the letters, for example, we can form "act", "cat" from the letters - "atc".

So we can build the HashMap from the dictionary, the key would be the sorted letters; the value would be a list containing all words that can be constructed by rearranging the order of these letters.

Code:

The complete algorithm/test code and also many other algorithm problems and solutions are available from https://github.com/programmer-plus.

package org.codeexample.algorithm.wordPuzzles;
import java.io.*;
import java.util.*;
import java.util.regex.Pattern;

public class Dictionary {

    private Map<String, HashSet<String>> wordMap = new HashMap<>();

    /**
     * @param dictionaryFile, the file contains list of words, 
     * each line may contain several words that are separated by space.
     * @throws IOException
     */
    public Dictionary(String dictionaryFile) throws IOException {
        init(dictionaryFile);
    }

    private void init(String dictionaryFile) throws IOException {
        FileReader fr = new FileReader(new File(dictionaryFile));

        FileReader fr = new FileReader(file);
        BufferedReader br = new BufferedReader(fr);

        Pattern pattern = Pattern.compile("\\s+");
        while (true) {
            String line = br.readLine();
            if (line == null) {
                break;
            }
            String[] words = pattern.split(line);
            for (String word : words) {
                word = word.trim();
                if (!word.isEmpty()) {
                    String sortedWord = getMapKey(word);

                    HashSet<String> matchedWordSet = wordMap.get(sortedWord);
                    if (matchedWordSet == null) {
                        matchedWordSet = new HashSet<>();
                    }
                    matchedWordSet.add(word);
                    wordMap.put(sortedWord, matchedWordSet);
                }
            }
        }
    }

    private String getMapKey(String letters) {
        char[] chars = letters.toCharArray();
        Arrays.sort(chars);
        return String.valueOf(chars);
    }

    /**
     * Return a list of word that can constructed by rearranging these letters.
     * 
     * @param letters
     * @return a hash set that containing all words, if can't find one, return
     *         empty list, instead of null to avoid NPE in client code.
     * @throws IllegalArgumentException if parameter is null.
     */
    public Set<String> formWords(String letters) 
            throws IllegalArgumentException {
        if (letters == null) {
            throw new IllegalArgumentException("parameter can't be null.");
        }
        Set<String> wordsSet = wordMap.get(getMapKey(letters));
        if (wordsSet == null) {
            wordsSet = new HashSet<>();
        }
        return wordsSet;
    }
}