Telephone Combinations

Given a telephone keypad, and an int number, print all words which are possible by pressing these numbers, the output strings should be sorted.

{0 : "", 1 : "", 2 : "abc", 3 : "def", 4 : "ghi", 5 : "jkl", 6 : "mno", 7 : "pqrs", 8 : "tuv", 9 : "wxyz"}

Assumptions:

• The given number >= 0

Examples:

if input number is 231, possible words which can be formed are:

[ad, ae, af, bd, be, bf, cd, ce, cf]

Solution: DFS of mapped strings

Pre-process number into corresponding String List

DFS:

Each level represent one string, one recursive call for each char of string

Hits bottom when no more string to process. Return current word combo

public class Solution {
  public String[] combinations(int number) {
    //sort number into descending order
    //dfs
    Map<Integer, String> keypad = new HashMap<>();
    keypad.put(2, "abc");
    keypad.put(3, "def");
    keypad.put(4, "ghi");
    keypad.put(5, "jkl");
    keypad.put(6, "mno");
    keypad.put(7, "pqrs");
    keypad.put(8, "tuv");
    keypad.put(9, "wxyz");

    String temp = Integer.toString(number);
    List<String> chars = new ArrayList<>();
    for (int i = 0; i < temp.length(); i++){
      char cur = temp.charAt(i);
      if (cur != '0' && cur != '1'){
        Integer key = cur - '0';
        String value = keypad.get(key);
        chars.add(value);
      }
    }

    StringBuilder sb = new StringBuilder();
    List<String> results = new ArrayList<>();
    helper(chars, 0, sb, results);

    String[] finalResults = new String[results.size()];
    finalResults = results.toArray(finalResults);
    return finalResults;
  }

  private void helper(List<String> chars, int index, StringBuilder sb, List<String> results){
    if (index == chars.size() ) {
      results.add(sb.toString());
      return;
    }

    String cur = chars.get(index);

    for (int i = 0; i < cur.length(); i++){
      //for each letter
      sb.append(cur.charAt(i));
      helper(chars, index + 1, sb, results);
      sb.deleteCharAt(sb.length() - 1);
    }
  }
}

TC:

Integer -> List<String> : number length * O(1) HashMap lookup = O(1)

Helper:N! permutations * N to String = O(N! * N)

SC:

Stack: depth = O( number length )

Heap: result = O(N!)