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.

telphone

Input:Digit string "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

首先对应这个题目可以这样考虑，对应的数字上的字母去出，然后对每个数字for循环for循环的层数，作为判断递归的出口。

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class Solution17 {
    static LinkedList<Character> list = new LinkedList<>();
    static List<String> result = new ArrayList<String>();

    public List<String> letterCombinations(String digits) {
        result.clear();
        String[] map = new String[10];
        map[0] = "";
        map[1] = "";
        map[2] = "abc";
        map[3] = "def";
        map[4] = "ghi";
        map[5] = "jkl";
        map[6] = "mno";
        map[7] = "pqrs";
        map[8] = "tuv";
        map[9] = "wxyz";
        LinkedList<char[]> tmp = new LinkedList<>();
        char[] chars = digits.toCharArray();
        String str="";
        for (int j = 0; j < chars.length; j++) {
            if (chars[j] == ' ') {
                str = map[0];
            } else {
                str = map[Integer.parseInt(chars[j] + "")];
            }
            tmp.add(str.toCharArray());//在tmp,里面存放每个数字对应的字符串数组
        }
        helper(map, 0, tmp);
        return result;
    }

    private void helper(String[] map, int n, LinkedList<char[]> tmp) {
        if (n == tmp.size()) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < list.size(); i++) {
                sb.append(list.get(i));
            }
            if (!sb.toString().equals("")) {
                result.add(sb.toString());
            }
            return;
        }
        for (int i = 0; i < tmp.get(n).length; i++) {
            list.add(tmp.get(n)[i]);
            helper(map, n + 1, tmp);
            list.pollLast();
        }

    }

    public static void main(String[] args) {
        new Solution17().letterCombinations("23");
        System.out.println(result);
    }

}