Print out all possible letter combinations a given phone number can represent

Question

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(n³).

public class LetterCombinationsOfPhoneNumber {
  private static final HashMap<Character, String> 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");
  };

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

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

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

Answer 1

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)

Answer 2

IMO there is a better way.

Firstly you store every combination in a List. You are doing more than what is asked by giving the possibility to use an arbitrary phone numbers length but you will eventually run out of memory past a certain length.

Secondly you are able to know beforehand the numbers of possibilities you will have so you do not need to go for a double or triple for loop.

So how to do it in one loop in java :

public class LetterCombination {
    // Mappings from 0 to 9.
    // With 0 and 1 with no mappings because none is given in our instructions
    public static String mappings[][] = {
        {""}, {""}, {"A", "B", "C"}, {"D", "E", "F"}, {"G", "H", "I"},
        {"J", "K", "L"}, {"M", "N", "O"}, {"P", "Q", "R", "S"}, 
        {"T", "U", "V"}, {"W", "X", "Y", "Z"}
    };

  public static void letterCombinations(String digits) {
      // The exercise specify that we will receive a phone number of 7 digits.
      // We suppose that the validation of the String received is done before.
      // All our digits are converted to int.
      int firstDigit = Integer.parseInt(digits.substring(0,1));
      int secondDigit = Integer.parseInt(digits.substring(1,2));
      int thirdDigit = Integer.parseInt(digits.substring(2,3));
      int fourthDigit = Integer.parseInt(digits.substring(3,4));
      int fifthDigit = Integer.parseInt(digits.substring(4,5));
      int sixthDigit = Integer.parseInt(digits.substring(5,6));
      int seventhDigit = Integer.parseInt(digits.substring(6,7));

      // To each digits is associated its number of possibilities
      // (From 3 to 4 in our exercise)
      int firstDigitPossibilities = mappings[firstDigit].length;
      int secondDigitPossibilities = mappings[secondDigit].length;
      int thirdDigitPossibilities = mappings[thirdDigit].length;
      int fourthDigitPossibilities = mappings[fourthDigit].length;
      int fifthDigitPossibilities = mappings[fifthDigit].length;
      int sixthDigitPossibilities = mappings[sixthDigit].length;
      int seventhDigitPossibilities = mappings[seventhDigit].length;

      // We will have between 3^7 and 4^7 iterations
      // We can have our number of iterations by multiplying each possibilities
      for(int i = 0; i < firstDigitPossibilities * secondDigitPossibilities * thirdDigitPossibilities * fourthDigitPossibilities * fifthDigitPossibilities * sixthDigitPossibilities * seventhDigitPossibilities ; i++) {

        // What is left is to print everything.
        // Last number is printed like this :
        //    * mappings[last Digit][i modulo last Digit possibilities]
        // Next Number is printed like this :
        //    * mapping [next Digit][( i / last Digit possibilities) modulo next Digit possibilities]
        // And so on...
        System.out.println(
            mappings[firstDigit][(i/(secondDigitPossibilities*thirdDigitPossibilities*fourthDigitPossibilities*fifthDigitPossibilities*sixthDigitPossibilities*seventhDigitPossibilities))%firstDigitPossibilities]
        + mappings[secondDigit][(i/thirdDigitPossibilities*fourthDigitPossibilities*fifthDigitPossibilities*sixthDigitPossibilities*seventhDigitPossibilities)%secondDigitPossibilities]
        + mappings[thirdDigit][(i/(fourthDigitPossibilities*fifthDigitPossibilities*sixthDigitPossibilities*seventhDigitPossibilities))%thirdDigitPossibilities]
        + mappings[fourthDigit][(i/(fifthDigitPossibilities*sixthDigitPossibilities*seventhDigitPossibilities))%fourthDigitPossibilities]
        + mappings[fifthDigit][(i/(sixthDigitPossibilities*seventhDigitPossibilities))%fifthDigitPossibilities]
        + mappings[sixthDigit][(i/(seventhDigitPossibilities))%sixthDigitPossibilities]
        + mappings[seventhDigit][i%seventhDigitPossibilities]);

    }
  }

  public static void main(String[] args) {
    letterCombinations("23456789");
  }
}