Letter Combinations of a Phone Number

Problem:

A phone pad has the number 2-9 maps to enlish characters as the following, 

    "2", "abc"

    "3", "def"

    "4", "ghi"

    "5", "jkl"

    "6", "mno"

    "7", "pqrs"

    "8", "tuv"

    "9", "wxyz"

Given a number, find all the possible lettters the given number can represent. The order of the letters doesn't matter.

For Example,

Given number : "23"

All the possible letters the number 23 can represent are: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

Solution:

We can use backtrack to find the answer. What passed in the recursive call is the remaining digits and the accumulative letters. Once the remaining digits are exausted, we meet the exit condition.

import java.util.*;
class Solution {
  public static void main(String[] args) {
    String letter = "23";
    Map<String, String> map = new HashMap<>();
    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");
    backTrace(letter, "", map);
  }

  private static void backTrace(String letter, String cur, Map<String, String> map) {
    if(letter.length() == 0) {
      System.out.print(cur + " ");
    } else {
      for(char c : map.get(letter.substring(0, 1)).toCharArray())
      backTrace(letter.substring(1), cur + c, map);
    }
  }
}

Time complexity O(N^3 * M^4), where N is the number of digits in the number that maps to 3 characters, and M is the number of digits in the number that maps to 4 characters.

The space complexity O(N^3 * M^4), because this is the total number of possible combinations.