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.

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

回溯法

说明

1. 返回条件： 当所得到的string长度与给入的string digits长度相同时候

2. 传入参数: 用一个数来记录string的长度, 每次递归传入长度+1和新的string

复杂度

假设有k个digit 每个digit可以代表m个字符, 时间O(m^k) 空间O(m^k)

代码

public List<String> letterCombinations(String digits) {
    List<String> res = new ArrayList<String>();
    if (digits == null || digits.length() == 0) {
        return res;
    }
    String[] map= {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    StringBuilder tem = new StringBuilder();
    helper(res, tem, digits, 0, map);
    return res;
}
public void helper(List<String> res, StringBuilder tem, String digits, int index, String[] map) {
    if (index == digits.length()) {
        res.add(tem.toString());
        return;
    }
    int m = digits.charAt(index) - '0';
    for (int i = 0; i < map[m].length(); i++) {
        tem.append(map[m].charAt(i));
        helper(res, tem, digits, index + 1, map);
        tem.deleteCharAt(tem.length() - 1);
    }
}