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&lt;String&gt; letterCombinations(String digits) {
        ArrayList&lt;String&gt; res = new ArrayList&lt;String&gt;();
        ArrayList&lt;String&gt; preres = new ArrayList&lt;String&gt;();
        res.add("");

        for (int i = 0; i &lt; digits.length(); i++) {
            for (String str : res) {
                String letters = map.get(digits.charAt(i));
                for (int j = 0; j &lt; letters.length(); j++)
                    preres.add(str + letters.charAt(j));
            }
            res = preres;
            preres = new ArrayList&lt;String&gt;();
        }
        return res;
    }

    static final HashMap&lt;Character, String&gt; map = new HashMap&lt;Character, String&gt;() {
        {
            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&lt;Character, String&gt; map = new HashMap&lt;&gt;(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&lt;String&gt; letterCombinations(String digits) {
    List&lt;String&gt; results = new ArrayList&lt;String&gt;();
    results.add("");

    for (int i = 0; i &lt; digits.length(); i++) {
        String letters = map.get(digits.charAt(i));
        List&lt;String&gt; nextResults = new ArrayList&lt;&gt;(letters.length() * results.size());
        for (String str : results) {
            for (int j = 0; j &lt; letters.length(); j++) {
                nextResults.add(str + letters.charAt(j));
            }
        }
        results = nextResults;
    }
    return results;
}




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

public static List&lt;String&gt; letterCombinations(String digits) {
    LinkedList&lt;String&gt; results = new LinkedList&lt;&gt;();
    results.add("");

    for (int i = 0; i &lt; digits.length(); i++) {
        String letters = map.get(digits.charAt(i));
        for (int j = results.size(); j &gt; 0; j--) {
            String intermediateResult = results.poll();
            for (int k = 0; k &lt; letters.length(); k++) {
                results.add(intermediateResult + letters.charAt(k));
            }
        }
    }
    return results;
}