Letter Combination of a Phone Number

Head on over here to try the problem for yourself.

Most permutation based problems seem to use a back-tracking solution, but don’t quote me on that 😅

Algorithm

The goal is to get all permutations of letters corresponding to a given phone number. First, we create a mapping of numbers and the corresponding letters. Then we simply set up a backtracking function helper() which will populate our result list with the required solutions.

Code

public List<String> letterCombinations(String digit) {
  List<String> result = new ArrayList();
  if(digits.length() == 0) return result;
  char[][] map = {
    {'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'}
  };

  StringBuilder curr = new StringBuilder();
  helper(result, curr, digits, map, 0);
  return result;
}

public void helper(List<String> result, StringBuilder curr, String digits, char[][] map, int index) {
  if(index >= digits.length()) {
    result.add(curr.toString());
    return;
  }
  for(char c : map[digits.charAt(i++) -'2']) {
    helper(result, curr.append(c), digits, map, i);
    curr.deleteCharAt(curr.length() - 1);
    // deleteCharAt() here makes the solution
    // move forward correctly in the for loop
  }
}