给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

image

示例:

<pre style="box-sizing: border-box; overflow: auto; font-family: Menlo, Monaco, Consolas, "Courier New", monospace; font-size: 13px; display: block; padding: 9.5px; margin: 0px 0px 10px; line-height: 1.42857; color: rgb(51, 51, 51); word-break: break-all; word-wrap: break-word; background-color: rgb(245, 245, 245); border: 1px solid rgb(204, 204, 204); border-radius: 4px; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;">输入："23"
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
</pre>

说明:
尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。

public static void main(String[] args) {
        List<String> list = letterCombinations("34");
        for (String string : list) {
            System.out.println(string);
        }
    }

    public static List<String> letterCombinations(String digits) {
        List<String> list = new ArrayList<String>();
        backTrack("", digits, 0, list);
        return list;
    }

    public static void backTrack(String s, String digits, int flag, List<String> list) {
        String[] dicts = { "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };
        if (flag >= digits.length()) {
            list.add(s);
            return;
        }

        String chars = dicts[digits.charAt(flag) - '0'];
        for (int i = 0; i < chars.length(); i++) {
            backTrack(s + chars.charAt(i), digits, flag + 1, list);
        }
    }