Print out all possible letter combinations a given phone number can represent I am working on a problem in which given a 7 digit telephone number, we need to print out all possible combinations of letters that each number could represent.

I came up with below code and I was wondering if there is any way to optimize it or if there is any better way? As of now complexity is O(n3).

public class LetterCombinationsOfPhoneNumber {
  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");
  };

  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;
  }

  public static void main(String[] args) {
    System.out.println(letterCombinations("23"));
  }
}
This can certainly be optimized.
Your algorithm works in loops that iterate over all permutations, placing one letter each time.
Let us take a different approach: 

The number of output combinations can be calculated in advanced: multiply the number of letters for all input numbers. in yout example ("23") the calculation is
number 2 has 3 letters
number 3 has 3 letters
output combinations will be 3*3=9  

Furthermore, we can calculate which letter will be placed in each combination based on the combination index. if we assume combination index goes from 0 to 8:
for number 2 (first number in input)
- combinations 0-2 will contain 1st letter
- combinations 3-5 will contain 2nd letter
- combinations 6-8 will contain 3rd letter
for number 3 (2nd number in input)
- combinations 0,3,6 will contain 1st letter
- combinations 1,4,7 will contain 2nd letter
- combinations 2,5,8 will contain 3rd letter  

so the formula for letter placement is based on the combination index, the position of the number in the input and the position of the letter in the letters-of-number String. 

the complexity of this algorithm is o(n*m) where n is number of input letters and m number of output combinations.

one comment regarding the code: You use the results as a Queue.  the LinkedList is an implementation of this interface. For clarity sake, the variable should be defined with the type that states its usage. This is also true for the map variable (should be defined as Map)