gistfile1.java

import java.util.Set;
import java.util.HashMap;
import java.util.HashSet;
import java.util.TreeSet;
import java.util.ArrayList;

public class Problem7_5 {
    static HashMap<Character, String> map;

    private static void prepareDictionary() {
        map = new HashMap<Character, String>();
        map.put('2', "abc");
        map.put('3', "def");
        map.put('4', "ghi");
        map.put('5', "jkl");
        map.put('6', "mno");
        map.put('7', "pqrs");
        map.put('8', "tuv");
        map.put('9', "wxyz");
    }

    public static HashSet<String> getWords(String sequence) {
        prepareDictionary();
        HashSet<String> words = new HashSet<String>();
        getWordsHelper(words, sequence, 0, "");

        return words;
    }

    private static void getWordsHelper(Set<String> words, String s, int index, String current) {
        if(index >= s.length()) {
            words.add(current);
            return;
        }

        char ch = s.charAt(index++);
        String letters = map.get(ch);
        for (char c: letters.toCharArray()) {
            String temp = current + c;
            getWordsHelper(words, s, index, temp);
        }
    }

    private static void test(String str) {
        System.out.println("Test sequence: " + str);
        Set<String> result = getWords(str);
        // I know, I know
        TreeSet<String> results = new TreeSet<String>(result);
        for (String s:results) {
            System.out.println(s);
        }
        System.out.println("Found " + results.size() + " results\n-------");
    }

    public static void main(String[] args) {
        test("3");
        test("2");
        test("23");
        test("22");
        test("345");
    }
}