3
\$\begingroup\$

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<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"));
  }
}
\$\endgroup\$
  • \$\begingroup\$ The number of outputs will be 3^n or more (not n^3), so that's obviously a lower bound on the complexity. You won't be able to get lower than that without omitting some of the results. \$\endgroup\$ – Toby Speight Oct 4 '18 at 7:43
  • \$\begingroup\$ One small hint regarding the new HashMap<>(8): in your case, it's not worth deciding on an initial capacity. And if you really care, you should start with a bigger capacity, as a new HashMap<>(8) will not accept 8 entries without growth, but only 6. The default load factor is 75%, meaning that the HashMap will grow as soon as it's 75% filled. \$\endgroup\$ – Ralf Kleberhoff Oct 4 '18 at 20:56
3
\$\begingroup\$

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)

\$\endgroup\$
  • \$\begingroup\$ good suggestion. can you provide an example in java so that I can understand better on how would this work? Also complexity will be same as my current solution? \$\endgroup\$ – dragons Oct 4 '18 at 15:18
2
\$\begingroup\$

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");
  }
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.