1、前言

题目描述

2、思路

递归思路

递归主要是递归数字代表的字符串，所以 start 应该代表 digits 的 index，每次查找出一个字符串的时候，对于查找的字符串 dict 应该从0开始，然后 dict 的当前字符加上 start + 1 后查找出来的字符串再去拼接。

3、代码

class Solution {

    private Map<Integer, String> phone = new HashMap<Integer, String>() {{
        put(2, "abc");
        put(3, "def");
        put(4, "ghi");
        put(5, "jkl");
        put(6, "mno");
        put(7, "pqrs");
        put(8, "tuv");
        put(9, "wxyz");
    }};

    private List<String> output = new ArrayList<String>();

    private int index = 0;

    public List<String> letterCombinations(String digits) {
        if(digits == null || digits.length() <= 0){
            return output;
        }

        backTravel("", 0, digits);
        return output;
    }

    private void backTravel(String str, int index, String digits){
        if(digits.length() == index){
            output.add(str);
            return;
        }

        int number = digits.charAt(index) - '0';
        String dict = phone.get(number);
        for(int i = 0; i < dict.length(); i++){
            backTravel(str + dict.charAt(i), index + 1, digits);
        }
    }

}