leetcode电话号码的字母组合

 自己没搞出来，只能借鉴别人实现，自己再实现了

 递归解法

 public class LetterCombinations {
    List<String> strings = new ArrayList<>();
    StringBuilder builder = new StringBuilder();

    public List<String> letterCombinations(String digits) {
        if(digits.isEmpty()) return strings;
        String[][] mapper = {{"a","b","c"},{"d","e","f"},{"g","h","i"},{"j","k","l"}
                ,{"m","n","o"},{"p","q","r","s"},{"t","u","v"},{"w","x","y","z"}};
        letterCombinations(mapper, 0, digits);
        return strings;
    }

    public void letterCombinations(String[][] mapper, int inx, String digits) {
        //这里是返回每个组合的关键，也是递归跳出的关键
        if(inx == digits.length()) {
            strings.add(builder.toString());
            return;
        }
        int index = digits.charAt(inx) - 50;
        for (int i = 0; i < mapper[index].length; i++) {
            builder.append(mapper[index][i]);
            letterCombinations(mapper, inx + 1, digits);
            //每次返回一个组合后，要把上次存进去的删掉，不然会串到一块
            builder.deleteCharAt(builder.length() - 1);
        }
    }
}

 非递归，直接遍历，一种巧妙的方式

    public static List<String> letterCombinations(String digits) {
        List<String> result = new ArrayList<>();
        if(digits == null || digits.length() == 0) {
            return result;
        }
        String[] mapping = new String[] {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        result.add("");
        for(int i = 0; i < digits.length(); i++) {
            List<String> temp = new ArrayList<>();
            String letters = mapping[digits.charAt(i) - '0'];
            for(int j = 0; j < letters.length(); j++) {
                //上一轮拼接结果和这一轮的字符拼接
                for(String s : result) {
                    temp.add(s + letters.charAt(j));
                }
            }
            //将上一轮拼接结果返回给下一轮去使用
            result = temp;
        }
        return result;
    }