LeetCode 17. Letter Combinations of a Phone Number

原题链接在这里：https://leetcode.com/problems/letter-combinations-of-a-phone-number/

题目：

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.

题解：

递归的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(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 }

类似Combinations, Generate Parentheses.