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/jefferyyuan/myAlgorithms.

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

public class Dictionary {

    private Map> 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 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 formWords(String letters)
            throws IllegalArgumentException {
        if (letters == null) {
            throw new IllegalArgumentException("parameter can't be null.");
        }
        Set wordsSet = wordMap.get(getMapKey(letters));
        if (wordsSet == null) {
            wordsSet = new HashSet<>();
        }
        return wordsSet;
    }
}


This article is migrated from my another blog: http://programmer-plus.blogspot.com/, but I found that I forgot my username for that blog. DARN!!!

Post a Comment

Labels

Java (159) Lucene-Solr (110) All (60) Interview (59) J2SE (53) Algorithm (37) Eclipse (35) Soft Skills (35) Code Example (31) Linux (26) JavaScript (23) Spring (22) Windows (22) Web Development (20) Tools (19) Nutch2 (18) Bugs (17) Debug (15) Defects (14) Text Mining (14) J2EE (13) Network (13) PowerShell (11) Chrome (9) Continuous Integration (9) How to (9) Learning code (9) Performance (9) UIMA (9) html (9) Design (8) Dynamic Languages (8) Http Client (8) Maven (8) Security (8) Trouble Shooting (8) bat (8) blogger (8) Big Data (7) Google (7) Guava (7) JSON (7) Problem Solving (7) ANT (6) Coding Skills (6) Database (6) Scala (6) Shell (6) css (6) Algorithm Series (5) Cache (5) IDE (5) Lesson Learned (5) Miscs (5) Programmer Skills (5) System Design (5) Tips (5) adsense (5) xml (5) AIX (4) Code Quality (4) GAE (4) Git (4) Good Programming Practices (4) Jackson (4) Memory Usage (4) OpenNLP (4) Project Managment (4) Python (4) Spark (4) Testing (4) ads (4) regular-expression (4) Android (3) Apache Spark (3) Become a Better You (3) Concurrency (3) Eclipse RCP (3) English (3) Firefox (3) Happy Hacking (3) IBM (3) J2SE Knowledge Series (3) JAX-RS (3) Jetty (3) Restful Web Service (3) Script (3) regex (3) seo (3) .Net (2) Android Studio (2) Apache (2) Apache Procrun (2) Architecture (2) Batch (2) Build (2) Building Scalable Web Sites (2) C# (2) C/C++ (2) CSV (2) Career (2) Cassandra (2) Distributed (2) Fiddler (2) Google Drive (2) Gson (2) Html Parser (2) Http (2) Image Tools (2) JQuery (2) Jersey (2) LDAP (2) Life (2) Logging (2) Software Issues (2) Storage (2) Text Search (2) xml parser (2) AOP (1) Application Design (1) AspectJ (1) Bit Operation (1) Chrome DevTools (1) Cloud (1) Codility (1) Data Mining (1) Data Structure (1) ExceptionUtils (1) Exif (1) Feature Request (1) FindBugs (1) Greasemonkey (1) HTML5 (1) Httpd (1) I18N (1) IBM Java Thread Dump Analyzer (1) JDK Source Code (1) JDK8 (1) JMX (1) Lazy Developer (1) Mac (1) Machine Learning (1) Mobile (1) My Plan for 2010 (1) Netbeans (1) Notes (1) Operating System (1) Perl (1) Problems (1) Product Architecture (1) Programming Life (1) Quality (1) Redhat (1) Redis (1) Review (1) RxJava (1) Solutions logs (1) Team Management (1) Thread Dump Analyzer (1) Troubleshooting (1) Visualization (1) boilerpipe (1) htm (1) ongoing (1) procrun (1) rss (1)

Popular Posts