力扣 17 电话号码的字母组合

题意：给定一个号码，找出该号码，每一个数字在电话上对应的字符串，可组成的所有可能的字符串

思路：

1. 把数字和数字对应的字符串放到一个string array里
2. DFS遍历每一种组合

思想：DFS

复杂度：时间O（n^2)，空间O(n)

class Solution {
    public List<String> letterCombinations(String digits) {
        String[] arr = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        List<String> res = new ArrayList();
        if(digits.length() == 0)
            return res;
        get(arr, 0, digits, "", res);
        return res;
    }
    void get(String[] arr, int index, String digits, String temp, List<String> res) {
        // 遍历完电话号码，得到一个合法组合，放到结果数组中
        if(index == digits.length()) {
            res.add(temp);
            return;
        }
       // 当前数字对应的字符串
        String cur = arr[(int)(digits.charAt(index) - '0')];
        // 是0和1的话就跳过，否则遍历当前字符串的每一个字符，对于每一个字符产生的新的字符串，继续进行DFS遍历，以得到所有的合法字符串
        if(cur.length() == 0) {
            get(arr, index+1, digits, temp, res);
        } else {
            for(int i=0;i<cur.length();i++) {
                get(arr, index+1, digits, temp + cur.charAt(i), res);
            }
        }
    }
}