Letter combinations of phone dial pad number

In preparation for interviews, I have written a solution to this question:


Given a sequence of numbers (34128) and an input map such as a dial
pad on a phone (2->[a,b,c], 3->[d,e,f], 4->[g,h,i]) write an algorithm
to return all possible words from the sequence. E.g. Input: 232
Output: [ada, adb, adc, aea, aeb, aec, afa, afb, afc, bda, bdb, bdc,
bea, beb, bec, bfa, bfb, bfc, cda, cdb, cdc, cea, ceb, cec, cfa, cfb,
cfc]


Also what will happen if this would have been a 12 digit international
number? How would that effect your design.

Below is the solution I have:

public class DialPad {

    public static void main(String[] args) {
        System.out.println(letterCombinations("232"));
    }

    public static ArrayList letterCombinations(String digits) {
        ArrayList res = new ArrayList();
        ArrayList preres = new ArrayList();
        res.add("");

        for (int i = 0; i ();
        }
        return res;
    }

    static final HashMap map = new HashMap() {
        {
            put('2', "abc");
            put('3', "def");
            put('4', "ghi");
            put('5', "jkl");
            put('6', "mno");
            put('7', "pqrs");
            put('8', "tuv");
            put('9', "wxyz");
        }
    };
}

Is there any improvement I can make here? It looks to me like complexity is high in this code. How can I simplify this code better?

Putting the members of this class in the reverse order (map, then letterCombinations(), then main()) would be more customary. The map should be private unless you have a good reason to do otherwise. I would also avoid creating an anonymous subclass of HashMap, and initialize it this way:

private static final HashMap map = new HashMap<>(8);
static {
    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");
};

It would be more obvious that preres is a temporary variable if you scoped it properly. Both res and preres could be named better — I've chosen results and nextResults, respectively.

Whenever possible, you should specify the initial capacity of an ArrayList. The penalty for underestimating can be rather severe, as it requires reallocating and copying existing results.

digits.charAt(i) is a loop invariant that can be moved from the middle loop into the outer one.

All loops should have braces. Omitting them is bad practice and will cause maintenance-induced bugs.

public static List letterCombinations(String digits) {
    List results = new ArrayList();
    results.add("");

    for (int i = 0; i  nextResults = new ArrayList<>(letters.length() * results.size());
        for (String str : results) {
            for (int j = 0; j < letters.length(); j++) {
                nextResults.add(str + letters.charAt(j));
            }
        }
        results = nextResults;
    }
    return results;
}

It's generally better to return List rather than ArrayList, to give you flexibility to change the implementation. For example, here is a solution that uses just one LinkedList.

public static List letterCombinations(String digits) {
    LinkedList results = new LinkedList<>();
    results.add("");

    for (int i = 0; i  0; j--) {
            String intermediateResult = results.poll();
            for (int k = 0; k < letters.length(); k++) {
                results.add(intermediateResult + letters.charAt(k));
            }
        }
    }
    return results;
}

StackExchange Code Review Q#91645, answer score: 4