原题链接在这里：https://leetcode.com/problems/letter-combinations-of-a-phone-number/
与Combinations极其相似，也是DFS用递归来做。
递归的stop condition 是index 达到 digits 的长度。e.g. "23", 开始index = 0, 加了一个字符后, index = 1, 再加一个 index = 2, 此时index == digits.length() 应该把sb加到res中，然后return.
每次加一个字符，这个字符数组是通过"23"中的对应数字，如2来确定的. n就是这个数字，可以用n来从keyBoard中找到对应的string.
Time Complexity: O(k^n), k是数字代表keyBoard中string的长度, n是digits的长度. Space(k^n).
AC Java:
1 public class Solution { 2 public List<String> letterCombinations(String digits) { 3 List<String> res = new ArrayList<String>(); 4 if(digits == null || digits.length() == 0){ 5 return res; 6 } 7 String [] keyBoard = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}; 8 dfs(digits, 0, new StringBuilder(), res, keyBoard); 9 return res; 10 } 11 12 private void dfs(String digits, int index, StringBuilder sb, List<String> res, String [] keyBoard){ 13 if(index == digits.length()){ 14 res.add(sb.toString()); 15 return; 16 } 17 int n = digits.charAt(index) - ‘0‘; //"23", index = 0, n = 2, 用来找对应keyBoard的string. 18 for(int i = 0; i<keyBoard[n].length(); i++){ 19 sb.append(keyBoard[n].charAt(i)); 20 dfs(digits, index+1, sb, res, keyBoard); 21 sb.deleteCharAt(sb.length()-1); 22 } 23 } 24 }
LeetCode Letter Combinations of a Phone Number
原文：http://www.cnblogs.com/Dylan-Java-NYC/p/4920053.html