[Timus] 1545 Hieroglyphs

Problem statement is here: http://acm.timus.ru/problem.aspx?space=1&num=1545

Slightly better than brute force solution to loop over the entire reference book for the input character is to store the reference book in a hashmap with key as the first character and then query the map in constant time for all the words starting with the character.

public class Task1545 {
    public void solve(int testNumber, InputReader in, OutputWriter out) {
        // Store the references pointed by the first character of the two
        // letter word.
        Map<Character, List<String>> refs = new HashMap<>();

        int n = in.nextInt();

        for (int i = 0; i < n; i++) {
            String ref = in.nextString();
            List<String> words = refs.getOrDefault(ref.charAt(0),
                                                   new ArrayList<>());
            words.add(ref);
            refs.put(ref.charAt(0), words);
        }

        Character letter = in.nextCharacter();

        List<String> matchingWords = refs.getOrDefault(letter,
                                                       new ArrayList<>());
        for (String matchingWord : matchingWords) {
            out.println(matchingWord);
        }
    }
}