Sunday, August 28, 2011

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;
    }
}

Labels

Review (572) System Design (334) System Design - Review (198) Java (189) Coding (75) Interview-System Design (65) Interview (63) Book Notes (59) Coding - Review (59) to-do (45) Linux (43) Knowledge (39) Interview-Java (35) Knowledge - Review (32) Database (31) Design Patterns (31) Big Data (29) Product Architecture (28) MultiThread (27) Soft Skills (27) Concurrency (26) Cracking Code Interview (26) Miscs (25) Distributed (24) OOD Design (24) Google (23) Career (22) Interview - Review (21) Java - Code (21) Operating System (21) Interview Q&A (20) System Design - Practice (20) Tips (19) Algorithm (17) Company - Facebook (17) Security (17) How to Ace Interview (16) Brain Teaser (14) Linux - Shell (14) Redis (14) Testing (14) Tools (14) Code Quality (13) Search (13) Spark (13) Spring (13) Company - LinkedIn (12) How to (12) Interview-Database (12) Interview-Operating System (12) Solr (12) Architecture Principles (11) Resource (10) Amazon (9) Cache (9) Git (9) Interview - MultiThread (9) Scalability (9) Trouble Shooting (9) Web Dev (9) Architecture Model (8) Better Programmer (8) Cassandra (8) Company - Uber (8) Java67 (8) Math (8) OO Design principles (8) SOLID (8) Design (7) Interview Corner (7) JVM (7) Java Basics (7) Kafka (7) Mac (7) Machine Learning (7) NoSQL (7) C++ (6) Chrome (6) File System (6) Highscalability (6) How to Better (6) Network (6) Restful (6) CareerCup (5) Code Review (5) Hash (5) How to Interview (5) JDK Source Code (5) JavaScript (5) Leetcode (5) Must Known (5) Python (5)

Popular Posts