Leetcode – Letter Combination 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"].1.看到这个题目，我们第一部想到的就是要按照数字存储相对应的字母。这样的话，显然array是一个比较好的选择。根据测试， 数字1和0都是对应空 “”。
2.因为是不同的组合，所以我们要从不同数字的对应字母里分别找出一个字母进行组合，这个就和leetcode里combination的题目很相似，应该用recursion来解
解题思路如下：
比如说我们输入23：
那么按照我们的习惯， 我们从2中的abc选一个a 再到3中的def选一个d 好，完成ab，放入list里面， 返回
                                     再到3中的def选一个e 好，完成ae，放入list里面 ，返回
　　　　　　　　　　　　　　　　　　　　　　再到3............f ...... af............ 返回，好了def里面我们已经结束了，返回到上一层的abc
                  我们从2中的abc选一个b
                                     ...............d .......bd............. 返回
　　　　　　　　　　　　　　　　　　　　　  ..............以此类推..................
　　　　　　　　　　　一直到我们遍历完abc
每当我们完成一个和数字组合相同的字符串 我们都存入list 并且return 并且返回到上层继续加入下一个属于同数字的字母
从上述我们可以看出recursion的逻辑

     public List<String> letterCombinations(String digits) {
         String[] letters = new String[]{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
         List<String> result = new ArrayList<>();
         if (digits.length() == 0) {
             return result;
         }
         formCombination(result, "", letters, 0, digits);
         return result;
     }
     void formCombination(List<String> result, String current, String[]letters, int index, String digits) {
         if (index >= digits.length() && current.length() == digits.length()) {
             result.add(current);
             return;
         }
         int digit = Integer.parseInt(digits.substring(index, index + 1));
         char[] arr = letters[digit].toCharArray();
         for (int j = 0; j < arr.length; j++) {
             formCombination(result, current + arr[j], letters, index + 1, digits);
         }
     }