LeetCode/17. 电话号码的字母组合

17. 电话号码的字母组合

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

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

示例 ：

输入："23"
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

来源：力扣（LeetCode）
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解：

本题我们都应该能想到回溯，但是由于每个数字对应多个字母，需要考虑到所有字母的排列组合。最直观能想到的就是for循环，比如digits为23，我们需要在第一层for循环里遍历2对应的abc，然后嵌套循环3对应的def，这是在我们知道digits情况下可以这么考虑。但题目给定的digits不定，此时我们就需要用到递归，每次先将数字对应的字母取出来，然后进行递归求解。

具体代码如下：

class Solution {
    //存放数字字母对应表
    HashMap<Character, String> map = new HashMap<>();
    List<String> result = new LinkedList<>();

    public List<String> letterCombinations(String digits) {
        if (digits.length() == 0)
            return result;
        map.put('2', "abc");
        map.put('3', "def");
        map.put('4', "ghi");
        map.put('5', "jkl");
        map.put('6', "mno");
        map.put('7', "pqrs");
        map.put('8', "tuv");
        map.put('9', "wxyz");
        StringBuilder track = new StringBuilder();
        backtrack(digits, track, 0, map);
        return result;
    }

    void backtrack(String digits, StringBuilder track, int start, Map<Character, String> map) {
        if (track.length() == digits.length()) {
            result.add(track.toString());
            return;
        }
		  //取出每个数字对应的字母
        String value = map.get(digits.charAt(start));
        for (int i = 0; i < value.length(); i++) {
            backtrack(digits, track.append(value.charAt(i)), start + 1, map);
            track.deleteCharAt(track.length() - 1);
        }
    }
}