Given a digit string, return all possible letter combinations that the number could represent.
A mapping of digit to letters (just like on the telephone buttons) is given below.
Input:Digit string "23" Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
Note: Although the above answer is in lexicographical order, your answer could be in any order you want.
Subscribe to see which companies asked this question.
My backtracking Solution:
public class Solution { static char[][] number = { {}, {}, { '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 List<String> letterCombinations(String digits) { char[] data = new char[digits.length()]; List<String> re = new ArrayList<String>(); if(digits.length()==0) return re; backtracking(0, digits.length(), digits, re, data); return re; } static void backtracking(int now, int target, String digits, List<String> re, char[] data) { if (now == target) { StringBuilder temp = new StringBuilder(); for (char c : data) temp.append(c); re.add(temp.toString()); return; } for (char c : number[digits.charAt(now) - 48]) { data[now] = c; backtracking(now + 1, target, digits, re, data); } } }