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"].
解:DFS 递归
public class Solution { public ArrayList<String> letterCombinations(String digits) { ArrayList<String> result = new ArrayList<String>(); if(digits.length() == 0){ result.add(""); return result; } String[] trans = new String[]{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}; convert(trans, result, 0, digits, ""); return result; } public void convert(String[] trans, ArrayList<String> result, int depth, String digits, String tmp){ if(depth == digits.length()){ result.add(tmp); return; } // ACSII码转int要减去48. int index = digits.charAt(depth) - 48; for(int i = 0; i < trans[index].length(); i++){ tmp += trans[index].charAt(i); convert(trans, result, depth+1, digits, tmp); tmp = tmp.substring(0, tmp.length()-1); } } }
ref:http://www.cnblogs.com/feiling/p/3185238.html