PhoneWords.java

package com.ever10.phonewords;

import java.util.*;
import java.util.stream.Collectors;

/**
 * Find possible words in a phone number using the standard keypad letter mapping, and a given dictionary of words (Set<String>).
 * <p>
 * Algorithm: Recursively discovers all matches by exhaustively finding all letter
 * combinations and matching against a word in the specified dictionary.
 * Multiple words are joined by a "-"
 * <p>
 * Created by rael on 04/09/15.
 */
public class PhoneWords {

    private final Dictionary dictionary;

    private static final Map<Integer, List<Character>> digitMap = new HashMap<>();

    static {
        digitMap.put(2, Arrays.asList('a', 'b', 'c'));
        digitMap.put(3, Arrays.asList('d', 'e', 'f'));
        digitMap.put(4, Arrays.asList('g', 'h', 'i'));
        digitMap.put(5, Arrays.asList('j', 'k', 'l'));
        digitMap.put(6, Arrays.asList('m', 'n', 'o'));
        digitMap.put(7, Arrays.asList('p', 'q', 'r', 's'));
        digitMap.put(8, Arrays.asList('t', 'u', 'v'));
        digitMap.put(9, Arrays.asList('w', 'x', 'y', 'z'));
    }

    public PhoneWords(Dictionary dictionary) {
        this.dictionary = dictionary;
    }

    public Set<String> getDictionaryWords(String phoneNumber) {
        return getDictionaryWords(phoneNumber.replaceAll("[^2-9]", ""), true, true);
    }

    private Set<String> getDictionaryWords(String number, boolean skipAllowedStart, boolean skipAllowedEnd) {
        if ("".equals(number)) return new HashSet<>();

        Set<String> words = new HashSet<>();
        List<String> permutations = digitMap.get(Character.digit(number.charAt(0), 10)).stream().map(Object::toString).collect(Collectors.toList());

        int numberLength = number.length();

        for (int i = 1; i < numberLength; i++) {
            permutations = getPermutations(permutations, Character.digit(number.charAt(i), 10));

            for (String word : permutations) {
                if (dictionary.contains(word)) {
                    if (i == numberLength - 1) {
                        words.add(word);
                    }
                    Set<String> nextWords = getDictionaryWords(number.substring(i + 1), true, true);
                    words.addAll(addWordPrefix(word, nextWords));
                } else if (skipAllowedStart && dictionary.contains(word.substring(1))) {
                    String substring = number.charAt(0) + word.substring(1);
                    if (i == numberLength - 1) {
                        words.add(substring);
                    }
                    Set<String> nextWords = getDictionaryWords(number.substring(i + 1), true, false);
                    words.addAll(addWordPrefix(substring, nextWords));
                } else if (skipAllowedEnd && dictionary.contains(word.substring(0, word.length() - 1))) {
                    String substring = word.substring(0, word.length() - 1) + number.charAt(word.length() - 1);
                    if (i == numberLength - 1) {
                        words.add(substring);
                    }
                    Set<String> nextWords = getDictionaryWords(number.substring(i + 1), false, true);
                    words.addAll(addWordPrefix(substring, nextWords));
                }
            }
        }
        return words;
    }

    private List<String> addWordPrefix(String word, Set<String> nextWords) {
        return nextWords.stream().map(nextWord -> word + "-" + nextWord).collect(Collectors.toList());
    }

    private List<String> getPermutations(List<String> permutations, Integer digit) {
        List<String> mutations = new ArrayList<>();
        for (Character character : digitMap.get(digit)) {
            List<String> characterPermutations = permutations.stream().map(p -> p + character).collect(Collectors.toList());
            mutations.addAll(characterPermutations);
        }
        return mutations;
    }

}