LeetCode 18 – Letter Combinations of a Phone Number

Solution to LeetCode Letter Combinations of a Phone Number problem.

This a simple recursion problem. To compute the translation of x:xs ¹, we get all possible translation of xs, say t(xs), and take all the translations of x, \(t(x)\), and compute the cartesian product \(t(x) \times t(xs)\).

public ArrayList<String> letterCombinations(String digits) {
  HashMap<Integer, String[]> dict = new HashMap<Integer,String[]>();
  dict.put(2, new String[]{"a","b","c"});
  dict.put(3, new String[]{"d","e","f"});
  dict.put(4, new String[]{"g","h","i"});
  dict.put(5, new String[]{"j","k","l"});
  dict.put(6, new String[]{"m","n","o"});
  dict.put(7, new String[]{"p","q","r","s"});
  dict.put(8, new String[]{"t","u","v"});
  dict.put(9, new String[]{"w","x","y","z"});
  dict.put(0, new String[]{" "});
  return letterCombinations(digits, dict);
}

private ArrayList<String> letterCombinations(String digits, HashMap<Integer,String[]> dict){
  ArrayList<String> result = new ArrayList<String>();
  if(digits.length() == 0){
    result.add("");
    return result;
  }
  int first = Integer.parseInt(digits.substring(0,1));
  if(digits.length() == 1){
    return new ArrayList(Arrays.asList(dict.get(first)));
  }
  else{
    ArrayList<String> firstChoices = letterCombinations(digits.substring(0,1),dict);
    ArrayList<String> tailChoices = letterCombinations(digits.substring(1),dict);
    for(String s1 : firstChoices){
      for(String s2 : tailChoices){
        result.add(s1+s2);
      }
    }
  }
  return result;
}

Letter Combinations of a Phone Number

This is notation for an iterable element where x is the first element, and xs is the rest of the iterable↩

LeetCode 18 – Letter Combinations of a Phone Number

Posted on December 25, 2013

Last updated on December 25, 2013